[IMPALA-2887] improve Bitmap with a fast mod

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Won't Fix
• Affects Version/s: Impala 2.3.0
• Component/s: Backend
• Labels: performance
• Target Version: Product Backlog
• Assignee: Unassigned
• Reporter: Zuo Wang
• Created: 26/Jan/16 07:03
• Updated: 23/Nov/17 00:16
• Resolved: 23/Nov/17 00:16

Description

The probe filter is fairly expensive. check the profile below.
This is due to the mod operator in Bitmap::Get<true>.
I will try to implement a fast mod according to "Division by Invariant Integers Using Multiplication"(T. Granlund and P. L. Montgomery, https://gmplib.org/~tege/divcnst-pldi94.pdf)

Function Stack Effective Time by Utilization Spin Time Overhead Time Effective Time Spin Time Overhead Time Instructions Retired: Total Instructions Retired: Self CPI Rate: Total CPI Rate: Self CPU Frequency Ratio: Total CPU Frequency Ratio: Self Module Function (Full) Source File Start Address
Total 98.9% 1.1% 0.0% 0.0% 0s 0s 100.0% 0 0.496 0.000 1.080 0.000
impala::HdfsParquetScanner::ScalarColumnReader<long, (bool)1>::ReadNonRepeatedValue 42.7% 0.0% 0.0% 4.1% 0s 0s 66.0% 1,944,000,000 0.329 1.041 1.108 1.081 impalad impala::HdfsParquetScanner::ScalarColumnReader<long, (bool)1>::ReadNonRepeatedValue(impala::MemPool*, impala::Tuple*, bool*) hdfs-parquet-scanner.cc 0xbf1560
ReadValue<false> 38.6% 0.0% 0.0% 0.0% 0s 0s 64.1% 14,400,000 0.307 0.250 1.111 impalad ReadValue<false> hdfs-parquet-scanner.cc 0xbf156d
ReadSlot<false> 37.8% 0.0% 0.0% 7.4% 0s 0s 64.0% 4,989,600,000 0.302 0.768 1.116 1.139 impalad ReadSlot<false> hdfs-parquet-scanner.cc 0xbf15a2
Get<true> 26.6% 0.0% 0.0% 26.6% 0s 0s 52.4% 52,192,800,000 0.259 0.259 1.114 1.114 impalad Get<true> bitmap.h 0xbf15e2