[COLLECTIONS-823] BloomFilter: Optimize ArrayCountingBloomFilter.ForEachBitMap

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Done
• Affects Version/s: 4.5.0-M1
• Fix Version/s: 4.5.0-M1
• Component/s: Collection
• Labels: bloom-filter
• Assignee: Claude Warren
• Reporter: Claude Warren
• Created: 15/Jun/22 08:25
• Updated: 06/Jul/22 06:59
• Resolved: 06/Jul/22 06:59

Description

 
 
Member

aherbert on 27 Feb

This converts all the non zero indices to a bitmap long[] array. But to do so requires using the forEachIndex method with a conditional boolean check on each loop iteration. I wonder if this should be brought inline for efficiency:

     @Override
    public boolean forEachBitMap(LongPredicate consumer) {
        Objects.requireNonNull(consumer, "consumer");
        long[] result = new long[BitMap.numberOfBitMaps(shape.getNumberOfBits())];
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] != 0) {
                // Avoids a second check on the predicate result in forEachIndex
                BitMap.set(result, i);
            }
        }
        return BitMapProducer.fromBitMapArray(result).forEachBitMap(consumer);
    }

Or better yet, avoid the long[] array:

        int blocksm1 = BitMap.numberOfBitMaps(shape.getNumberOfBits()) - 1;
        int i = 0;
        long value;
        for (int j = 0; j < blocksm1; j++) {
            value = 0;
            for (int k = 0; k < Long.SIZE; k++) {
                if (counts[i++] != 0) {
                    value |= BitMap.getLongBit(k);
                }
            }
            if (!consumer.test(value)) {
                return false;
            }
        }
        // Final block
        value = 0;
        for (int k = 0; i < counts.length; k++) {
            if (counts[i++] != 0) {
                value |= BitMap.getLongBit(k);
            }
        }
        return consumer.test(value);

Issue Links

• is a child of: COLLECTIONS-728 BloomFilter contribution