[
https://issues.apache.org/jira/browse/LUCENE-2221?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12802972#action_12802972
]
Yonik Seeley commented on LUCENE-2221:
--------------------------------------
bq. Results from Intel I7 - an improvement of about 20%. Significant, but I was
silently hoping for more.
Remember, pop_array and friends do tricks to only call pop once for every 8
longs because pop was slow...
for the intrinsic case, did you try a simple loop that calls pop for every
element? For example:
{code}
public static long pop_intersect_simple(long A[], long B[], int wordOffset,
int numWords) {
int end = wordOffset + numWords;
long ret = 0;
for (int i=wordOffset; i<end; i++) {
ret += Long.bitCount(A[i]^B[i]);
}
return ret;
}
{code}
> Micro-benchmarks for ntz and pop (BitUtils) operations.
> -------------------------------------------------------
>
> Key: LUCENE-2221
> URL: https://issues.apache.org/jira/browse/LUCENE-2221
> Project: Lucene - Java
> Issue Type: Task
> Components: Other
> Reporter: Dawid Weiss
> Priority: Trivial
> Attachments: benchmark.jar, benchmarks.txt,
> lucene-bitset-benchmarks.zip, results-popntz.txt
>
>
> As suggested by Yonik, I performed a suite of micro-benchmarks to investigate
> the following:
> * pop() (bitCount) seems to be implemented in the same way ("hacker's
> delight") as in the BitUtils class (SUN's standard library from version 1.5).
> * native intrinsics have been recently added to the HotSpot that should speed
> up bitCount significantly.
> I have tried to run the code on various VMs and architectures, but of course
> the results may vary depending on the setting.
> h2. Micro-benchmark code, evaluation
> * The micro-benchmarks were written as JUnit tests with a custom set of rules
> that repeats each test measuring execution time, gc use, etc.
> * There were 5 warmup runs before each test, followed by 15 benchmarked runs.
> The result contain overall times, round times and standard deviations where
> applicable.
> * There were several tests for isolated performance of {{BitUtil.pop()}},
> JDK's {{bitCount}}, {{BitUtil.ntz()}}, {{BitUtil.ntz2()}}, {{BitUtil.ntz3()}}
> and JDK's {{numberOfTrailingZeros}}, the test code had the following loop:
> {code}
> final long [] longs = NtzPopBenchmark.random.bits;
> int cnt = 0;
> for (int i = longs.length; --i >= 0;)
> {
> cnt += Long.bitCount(longs[i]);
> }
> volatileVariable = cnt; // to prevent dead code removal.
> {code}
> * I also added another version of pop() based on a precomputed bit counts.
> This version was called {{pop2}}.
> * The input array of long values was initialized to a memory taking 200MB.
> There were two different sets: {{random}} (random values) and {{single}}
> (single bit rotated to the right in each long).
> * There were tests that called {{BitUtil.pop_xor}} between the two input
> bitsets (random, single).
> * Additional tests that used iterators and and other BitUtil operations
> showed similar performance to isolated loops, so I omit them here.
> h2. Evaluation environment
> I tested on three different machines:
> * Pentium 4, 32-bit, 3GHZ, 2GB RAM (Windows)
> * AMD Athlon(tm) 64 X2 Dual Core Processor 5200+, 64-bit, 4GB RAM (Ubuntu)
> * Intel(R) Core(TM)2 Quad CPU Q9650 @ 3.00GHz, 64-bit, 4GB RAM (Ubuntu)
> and on various VMs:
> * 1.6.0_17, Java HotSpot(TM) Server VM, 14.3-b01, Sun Microsystems Inc.,
> * 1.5.0_18, Java HotSpot(TM) Server VM, 1.5.0_18-b02, Sun Microsystems Inc.,
> * 1.7.0-ea, Java HotSpot(TM) Server VM, 17.0-b06, Sun Microsystems Inc.,
> * 1.6.0, IBM J9 VM, 2.4, IBM Corporation,
> * BEA JRockit.
> * (ant other minor versions of the VMs above, depending on the computer).
> h2. Results overview
> h3. {{pop}}
> The times between {{BitUtil}} and JDK were mostly identical. However, on
> 32-bit systems, precached {{pop2}} performed
> *much* better. Examples:
> {noformat}
> # 1.6.0_17, Java HotSpot(TM) Server VM, 14.3-b01, Sun Microsystems Inc.,
> test_POP_JDK_random : 15/20 rounds, time.total: 15.61, time.warmup:
> 4.31, time.bench: 11.30, round: 0.75 [+- 0.02]
> test_POP_JDK_single : 15/20 rounds, time.total: 15.67, time.warmup:
> 4.31, time.bench: 11.36, round: 0.76 [+- 0.02]
> test_POP_BitUtil_random : 15/20 rounds, time.total: 15.55, time.warmup:
> 4.33, time.bench: 11.22, round: 0.75 [+- 0.01]
> test_POP_BitUtil_single : 15/20 rounds, time.total: 15.55, time.warmup:
> 4.31, time.bench: 11.23, round: 0.75 [+- 0.01]
> test_POP2_random : 15/20 rounds, time.total: 6.69, time.warmup:
> 1.75, time.bench: 4.94, round: 0.33 [+- 0.00]
> test_POP2_single : 15/20 rounds, time.total: 4.66, time.warmup:
> 1.22, time.bench: 3.44, round: 0.23 [+- 0.01]
> {noformat}
> Note the difference between random and single distributions -- most probably
> due to more cache hits when referring to the
> lookup table. Other VMs on this 32-bit machine:
> {noformat}
> # 1.5.0_18, Java HotSpot(TM) Server VM, 1.5.0_18-b02, Sun Microsystems Inc.,
> test_POP_JDK_random : 15/20 rounds, time.total: 20.67, time.warmup:
> 5.19, time.bench: 15.48, round: 1.03 [+- 0.01]
> test_POP_JDK_single : 15/20 rounds, time.total: 22.70, time.warmup:
> 5.63, time.bench: 17.08, round: 1.14 [+- 0.01]
> test_POP_BitUtil_random : 15/20 rounds, time.total: 22.69, time.warmup:
> 5.63, time.bench: 17.06, round: 1.14 [+- 0.01]
> test_POP_BitUtil_single : 15/20 rounds, time.total: 20.67, time.warmup:
> 5.19, time.bench: 15.48, round: 1.03 [+- 0.01]
> test_POP2_random : 15/20 rounds, time.total: 6.30, time.warmup:
> 1.63, time.bench: 4.67, round: 0.31 [+- 0.01]
> test_POP2_single : 15/20 rounds, time.total: 4.33, time.warmup:
> 1.16, time.bench: 3.17, round: 0.21 [+- 0.01]
> # 1.7.0-ea, Java HotSpot(TM) Server VM, 17.0-b06, Sun Microsystems Inc.,
> test_POP_JDK_random : 15/20 rounds, time.total: 15.28, time.warmup:
> 4.25, time.bench: 11.03, round: 0.74 [+- 0.03]
> test_POP_JDK_single : 15/20 rounds, time.total: 15.16, time.warmup:
> 4.20, time.bench: 10.95, round: 0.73 [+- 0.01]
> test_POP_BitUtil_random : 15/20 rounds, time.total: 15.12, time.warmup:
> 4.20, time.bench: 10.92, round: 0.73 [+- 0.01]
> test_POP_BitUtil_single : 15/20 rounds, time.total: 15.13, time.warmup:
> 4.25, time.bench: 10.88, round: 0.73 [+- 0.01]
> test_POP2_random : 15/20 rounds, time.total: 6.78, time.warmup:
> 1.72, time.bench: 5.06, round: 0.34 [+- 0.01]
> test_POP2_single : 15/20 rounds, time.total: 4.72, time.warmup:
> 1.20, time.bench: 3.52, round: 0.23 [+- 0.02]
> {noformat}
> On 64-bit machines, the results are nearly equal, with pop2 performing
> slightly worse on SUN's 1.6 compared to JDK and BitUtil
> (but this difference is really tiny and not present on all VMs; see IBM J9
> and SUN's 1.5 below).
> {noformat}
> # 1.6.0_16, Java HotSpot(TM) 64-Bit Server VM, 14.2-b01, Sun Microsystems
> Inc.,
> test_POP_JDK_random : 15/20 rounds, time.total: 3.27, time.warmup:
> 0.81, time.bench: 2.46, round: 0.16 [+- 0.00]
> test_POP_JDK_single : 15/20 rounds, time.total: 3.11, time.warmup:
> 0.76, time.bench: 2.34, round: 0.16 [+- 0.02]
> test_POP_BitUtil_random : 15/20 rounds, time.total: 3.27, time.warmup:
> 0.81, time.bench: 2.46, round: 0.16 [+- 0.00]
> test_POP_BitUtil_single : 15/20 rounds, time.total: 3.03, time.warmup:
> 0.77, time.bench: 2.26, round: 0.15 [+- 0.00]
> test_POP2_random : 15/20 rounds, time.total: 3.63, time.warmup:
> 0.93, time.bench: 2.70, round: 0.18 [+- 0.00]
> test_POP2_single : 15/20 rounds, time.total: 3.51, time.warmup:
> 0.89, time.bench: 2.62, round: 0.17 [+- 0.00]
> # 1.6.0, IBM J9 VM, 2.4, IBM Corporation,
> test_POP_JDK_random : 15/20 rounds, time.total: 4.80, time.warmup:
> 1.24, time.bench: 3.57, round: 0.24 [+- 0.01]
> test_POP_JDK_single : 15/20 rounds, time.total: 5.00, time.warmup:
> 1.44, time.bench: 3.56, round: 0.24 [+- 0.01]
> test_POP_BitUtil_random : 15/20 rounds, time.total: 4.81, time.warmup:
> 1.24, time.bench: 3.56, round: 0.24 [+- 0.01]
> test_POP_BitUtil_single : 15/20 rounds, time.total: 4.75, time.warmup:
> 1.19, time.bench: 3.56, round: 0.24 [+- 0.01]
> test_POP2_random : 15/20 rounds, time.total: 3.65, time.warmup:
> 0.90, time.bench: 2.76, round: 0.18 [+- 0.00]
> test_POP2_single : 15/20 rounds, time.total: 3.82, time.warmup:
> 0.93, time.bench: 2.89, round: 0.19 [+- 0.01]
> # 1.5.0_18, Java HotSpot(TM) 64-Bit Server VM, 1.5.0_18-b02, Sun Microsystems
> Inc.,
> test_POP_JDK_random : 15/20 rounds, time.total: 3.72, time.warmup:
> 0.94, time.bench: 2.78, round: 0.19 [+- 0.00]
> test_POP_JDK_single : 15/20 rounds, time.total: 5.96, time.warmup:
> 1.40, time.bench: 4.56, round: 0.30 [+- 0.00]
> test_POP_BitUtil_random : 15/20 rounds, time.total: 6.16, time.warmup:
> 1.43, time.bench: 4.73, round: 0.31 [+- 0.00]
> test_POP_BitUtil_single : 15/20 rounds, time.total: 3.62, time.warmup:
> 0.92, time.bench: 2.70, round: 0.18 [+- 0.00]
> test_POP2_random : 15/20 rounds, time.total: 3.70, time.warmup:
> 0.96, time.bench: 2.74, round: 0.18 [+- 0.00]
> test_POP2_single : 15/20 rounds, time.total: 3.57, time.warmup:
> 0.93, time.bench: 2.65, round: 0.18 [+- 0.00]
> {noformat}
> The other 64-bit machine (quad-core):
> {noformat}
> # 1.7.0-ea, Java HotSpot(TM) 64-Bit Server VM, 17.0-b06, Sun Microsystems
> Inc.,
> test_POP_JDK_random : 15/20 rounds, time.total: 2.46, time.warmup:
> 0.62, time.bench: 1.84, round: 0.12 [+- 0.00]
> test_POP_JDK_single : 15/20 rounds, time.total: 2.49, time.warmup:
> 0.62, time.bench: 1.87, round: 0.12 [+- 0.01]
> test_POP_BitUtil_random : 15/20 rounds, time.total: 2.47, time.warmup:
> 0.62, time.bench: 1.84, round: 0.12 [+- 0.00]
> test_POP_BitUtil_single : 15/20 rounds, time.total: 2.46, time.warmup:
> 0.62, time.bench: 1.84, round: 0.12 [+- 0.00]
> test_POP2_random : 15/20 rounds, time.total: 2.82, time.warmup:
> 0.71, time.bench: 2.11, round: 0.14 [+- 0.00]
> test_POP2_single : 15/20 rounds, time.total: 2.15, time.warmup:
> 0.55, time.bench: 1.61, round: 0.11 [+- 0.00]
> {noformat}
> I then replaced {{BitUtil.pop}} with {{BitUtil.pop2}} in bit-counting methods
> like xor/and/or. The results are intriguing.
> On 32-bit systems, there is a measureable gain, like here:
> {noformat}
> # 1.6.0_17, Java HotSpot(TM) Server VM, 14.3-b01, Sun Microsystems Inc.,
> test_pop_xor : 15/20 rounds, time.total: 9.78, time.warmup:
> 2.59, time.bench: 7.19, round: 0.48 [+- 0.01]
> test_pop2_hd_xor : 15/20 rounds, time.total: 8.27, time.warmup:
> 2.22, time.bench: 6.05, round: 0.40 [+- 0.01]
> # 1.7.0-ea, Java HotSpot(TM) Server VM, 17.0-b06, Sun Microsystems Inc.,
> test_pop_xor : 15/20 rounds, time.total: 9.89, time.warmup:
> 2.59, time.bench: 7.30, round: 0.49 [+- 0.02]
> test_pop2_hd_xor : 15/20 rounds, time.total: 8.20, time.warmup:
> 2.24, time.bench: 5.97, round: 0.40 [+- 0.01]
> {noformat}
> On 64-bit systems, when 64-bit values can be manipulated directly in
> registers, there was nearly no speedup or even
> a small performance penalty like in here:
> {noformat}
> # 1.7.0-ea, Java HotSpot(TM) 64-Bit Server VM, 17.0-b06, Sun Microsystems
> Inc.,
> test_pop_xor : 15/20 rounds, time.total: 1.76, time.warmup:
> 0.49, time.bench: 1.27, round: 0.09 [+- 0.00]
> test_pop2_hd_xor : 15/20 rounds, time.total: 2.06, time.warmup:
> 0.55, time.bench: 1.51, round: 0.10 [+- 0.00]
> {noformat}
> I'm guessing referencing memory on this fast processors is slower than
> manipulating registers.
> h3. {{ntz}}
> On JVMs prior to 1.7, the {{ntz} version from Lucene was much faster in my
> tests than the one from JDK,
> but it also has a greater variance depending on the input bits' distribution
> (compare the same routine
> for random and single below).
> {noformat}
> # 32-bit system;
> # 1.6.0_17, Java HotSpot(TM) Server VM, 14.3-b01, Sun Microsystems Inc.,
> test_NTZ_JDK_random : 15/20 rounds, time.total: 6.69, time.warmup:
> 1.73, time.bench: 4.95, round: 0.33 [+- 0.01]
> test_NTZ_JDK_single : 15/20 rounds, time.total: 7.59, time.warmup:
> 1.94, time.bench: 5.66, round: 0.38 [+- 0.01]
> test_NTZ_BitUtil_random : 15/20 rounds, time.total: 2.72, time.warmup:
> 0.73, time.bench: 1.98, round: 0.13 [+- 0.02]
> test_NTZ_BitUtil_single : 15/20 rounds, time.total: 5.28, time.warmup:
> 1.34, time.bench: 3.94, round: 0.26 [+- 0.02]
> test_NTZ2_BitUtil_random : 15/20 rounds, time.total: 3.06, time.warmup:
> 0.81, time.bench: 2.25, round: 0.15 [+- 0.01]
> test_NTZ2_BitUtil_single : 15/20 rounds, time.total: 5.36, time.warmup:
> 1.34, time.bench: 4.02, round: 0.27 [+- 0.01]
> test_NTZ3_BitUtil_random : 15/20 rounds, time.total: 5.80, time.warmup:
> 1.48, time.bench: 4.31, round: 0.29 [+- 0.01]
> test_NTZ3_BitUtil_single : 15/20 rounds, time.total: 6.98, time.warmup:
> 1.81, time.bench: 5.17, round: 0.34 [+- 0.01]
> # 64-bit Athlon
> # 1.6.0_16, Java HotSpot(TM) 64-Bit Server VM, 14.2-b01, Sun Microsystems
> Inc.,
> test_NTZ_JDK_random : 15/20 rounds, time.total: 4.59, time.warmup:
> 1.16, time.bench: 3.44, round: 0.23 [+- 0.00]
> test_NTZ_JDK_single : 15/20 rounds, time.total: 6.64, time.warmup:
> 1.59, time.bench: 5.04, round: 0.34 [+- 0.01]
> test_NTZ_BitUtil_random : 15/20 rounds, time.total: 2.09, time.warmup:
> 0.53, time.bench: 1.56, round: 0.10 [+- 0.00]
> test_NTZ_BitUtil_single : 15/20 rounds, time.total: 3.87, time.warmup:
> 0.98, time.bench: 2.90, round: 0.19 [+- 0.00]
> test_NTZ2_BitUtil_random : 15/20 rounds, time.total: 2.09, time.warmup:
> 0.52, time.bench: 1.57, round: 0.10 [+- 0.00]
> test_NTZ2_BitUtil_single : 15/20 rounds, time.total: 3.31, time.warmup:
> 0.84, time.bench: 2.47, round: 0.16 [+- 0.00]
> test_NTZ3_BitUtil_random : 15/20 rounds, time.total: 3.31, time.warmup:
> 0.83, time.bench: 2.48, round: 0.17 [+- 0.00]
> test_NTZ3_BitUtil_single : 15/20 rounds, time.total: 5.71, time.warmup:
> 1.39, time.bench: 4.32, round: 0.29 [+- 0.00]
> {noformat}
> But then comes the 1.7 HotSport and things change radically, on 32-bit system
> the JDK's version is much faster for nearly-empty
> {{long}} values:
> {noformat}
> # 1.7.0-ea, Java HotSpot(TM) Server VM, 17.0-b06, Sun Microsystems Inc.,
> test_NTZ_JDK_random : 15/20 rounds, time.total: 1.97, time.warmup:
> 0.61, time.bench: 1.36, round: 0.09 [+- 0.01]
> test_NTZ_JDK_single : 15/20 rounds, time.total: 2.53, time.warmup:
> 0.77, time.bench: 1.77, round: 0.12 [+- 0.01]
> test_NTZ_BitUtil_random : 15/20 rounds, time.total: 2.36, time.warmup:
> 0.66, time.bench: 1.70, round: 0.11 [+- 0.01]
> test_NTZ_BitUtil_single : 15/20 rounds, time.total: 4.50, time.warmup:
> 1.19, time.bench: 3.31, round: 0.22 [+- 0.01]
> test_NTZ2_BitUtil_random : 15/20 rounds, time.total: 3.08, time.warmup:
> 0.81, time.bench: 2.27, round: 0.15 [+- 0.01]
> test_NTZ2_BitUtil_single : 15/20 rounds, time.total: 4.97, time.warmup:
> 1.28, time.bench: 3.69, round: 0.25 [+- 0.01]
> test_NTZ3_BitUtil_random : 15/20 rounds, time.total: 5.78, time.warmup:
> 1.48, time.bench: 4.30, round: 0.29 [+- 0.01]
> test_NTZ3_BitUtil_single : 15/20 rounds, time.total: 7.77, time.warmup:
> 1.91, time.bench: 5.86, round: 0.39 [+- 0.01]
> {noformat}
> On the 64-bit quad core:
> {noformat}
> # 1.6.0_13, Java HotSpot(TM) 64-Bit Server VM, 11.3-b02, Sun Microsystems
> Inc.,
> test_NTZ_JDK_random : 15/20 rounds, time.total: 3.92, time.warmup:
> 0.97, time.bench: 2.94, round: 0.20 [+- 0.00]
> test_NTZ_JDK_single : 15/20 rounds, time.total: 3.80, time.warmup:
> 0.97, time.bench: 2.82, round: 0.19 [+- 0.00]
> test_NTZ_BitUtil_random : 15/20 rounds, time.total: 0.96, time.warmup:
> 0.25, time.bench: 0.71, round: 0.05 [+- 0.00]
> test_NTZ_BitUtil_single : 15/20 rounds, time.total: 2.74, time.warmup:
> 0.69, time.bench: 2.04, round: 0.14 [+- 0.00]
> test_NTZ2_BitUtil_random : 15/20 rounds, time.total: 1.22, time.warmup:
> 0.31, time.bench: 0.91, round: 0.06 [+- 0.00]
> test_NTZ2_BitUtil_single : 15/20 rounds, time.total: 2.18, time.warmup:
> 0.56, time.bench: 1.62, round: 0.11 [+- 0.00]
> test_NTZ3_BitUtil_random : 15/20 rounds, time.total: 2.76, time.warmup:
> 0.71, time.bench: 2.06, round: 0.14 [+- 0.00]
> test_NTZ3_BitUtil_single : 15/20 rounds, time.total: 3.47, time.warmup:
> 0.91, time.bench: 2.56, round: 0.17 [+- 0.01]
> {noformat}
> And then comes the 1.7, compare JDK's implementation with anything else
> (especially the {{time.bench}} for
> the {{single}} input data. Looks like this is hardware-accelerated.
> {noformat}
> # -server -Xbatch -Xmx1024m
> # 1.7.0-ea, Java HotSpot(TM) 64-Bit Server VM, 17.0-b06, Sun Microsystems
> Inc.,
> test_NTZ_JDK_random : 15/20 rounds, time.total: 0.79, time.warmup:
> 0.21, time.bench: 0.58, round: 0.04 [+- 0.00]
> test_NTZ_JDK_single : 15/20 rounds, time.total: 0.75, time.warmup:
> 0.20, time.bench: 0.55, round: 0.04 [+- 0.00]
> test_NTZ_BitUtil_random : 15/20 rounds, time.total: 0.98, time.warmup:
> 0.25, time.bench: 0.72, round: 0.05 [+- 0.00]
> test_NTZ_BitUtil_single : 15/20 rounds, time.total: 2.61, time.warmup:
> 0.66, time.bench: 1.95, round: 0.13 [+- 0.00]
> test_NTZ2_BitUtil_random : 15/20 rounds, time.total: 1.30, time.warmup:
> 0.33, time.bench: 0.97, round: 0.06 [+- 0.00]
> test_NTZ2_BitUtil_single : 15/20 rounds, time.total: 2.48, time.warmup:
> 0.61, time.bench: 1.88, round: 0.13 [+- 0.00]
> test_NTZ3_BitUtil_random : 15/20 rounds, time.total: 2.81, time.warmup:
> 0.70, time.bench: 2.11, round: 0.14 [+- 0.00]
> test_NTZ3_BitUtil_single : 15/20 rounds, time.total: 4.07, time.warmup:
> 1.02, time.bench: 3.05, round: 0.20 [+- 0.00]
> {noformat}
> h2. Conclusions
> It seems that any change introduced to these routines will hurt somebody in
> some configuration, so it's really hard
> for me to make choices. I would definitely opt for the precached {{pop2}}
> version on 32-bit systems as it seems to
> be always faster or equally fast compared to other bit counting options.
> {{pop2}} looked like this:
> {code}
> private static byte [] bcounts = new byte [0x10000];
> static
> {
> for (int i = 0x10000; --i >= 0;)
> bcounts[i] = (byte) Integer.bitCount(i);
> }
> public static int pop2(long v)
> {
> int t;
> return
> bcounts[(t = (int) v) & 0xffff]
> + bcounts[t >>> 16]
> + bcounts[(t = ((int) (v >>> 32))) & 0xffff]
> + bcounts[t >>> 16];
> }
> {code}
> As for the hardware-accelerated {{ntz}}, if one can detect 1.7, then using
> the JDK's version is speeding up things
> significantly. But I have not checked how this detection would affect speed
> if done at run-time (I assume a final
> static flag wouldn't cause any performance penalty) and it is definitely not
> worth replacing for folks with older
> VMs.
> h2. Raw results data.
> I will attach raw results as part of the issue if you want to draw your own
> conclusions. Didn't have access to sparc-machine
> or to any machine with the newest Intels.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: java-dev-h...@lucene.apache.org
