pjfanning commented on code in PR #3030: URL: https://github.com/apache/pekko/pull/3030#discussion_r3557426580
########## stream/src/main/scala/org/apache/pekko/stream/impl/fusing/GraphInterpreter.scala: ########## @@ -13,6 +13,7 @@ package org.apache.pekko.stream.impl.fusing +import java.util.BitSet Review Comment: java.util.BitSet can have absolutely terrible performance java.util.BitSet has a few well-known performance characteristics that bite people in specific scenarios: Where it struggles Sparse bit patterns. BitSet allocates a long[] word array sized to the highest set bit. If you set bit 10,000,000 while only having a handful of bits set overall, you still pay for ~1.25MB of backing array. Iteration (nextSetBit) then has to skip over huge runs of zero words. Growth/resizing. Setting a bit beyond the current capacity triggers array reallocation and copy, similar to ArrayList — can be costly if you don't pre-size it via the constructor. Not thread-safe, so concurrent access requires external synchronization, which people sometimes don't realize until it's a bottleneck. Boxing/indirection overhead relative to raw primitive array manipulation, if you're doing very hot-loop bit twiddling — though this is usually minor compared to the sparse-layout issue. Common alternatives with sparse layouts RoaringBitmap — the most widely used one in the JVM ecosystem. It partitions the bit space into 2^16-sized "chunks" and picks the best internal representation per chunk (array of shorts for sparse, bitmap for dense, run-length encoding for runs). Excellent for both sparse and clustered-dense data, very fast unions/intersections/differences, and has great real-world adoption (Lucene, Spark, Druid, Elasticsearch all use it or a variant). JavaEWAH (Compressed bitmap) — word-aligned hybrid run-length encoding, good when you have long runs of zeros/ones, common in bitmap-index use cases (analytics/OLAP). Sparse hash-set-of-longs approaches (e.g. using a LongOpenHashSet from fastutil, or a custom compressed trie) if you genuinely just have a sparse handful of bits and don't need bitmap set-algebra. fastutil / Eclipse Collections primitive collections — not bitmaps per se, but relevant if BitSet was being (mis)used just as a compact int-set. Roaring64Bitmap / Roaring64NavigableMap — for when your bit indices exceed 32 bits. Rule of thumb Dense, bounded-range bits (e.g., flags over a known small universe) → BitSet is fine and often the fastest option due to JIT-friendly word operations. Sparse or very large/unbounded index space, or you need fast boolean set-algebra (AND/OR/XOR/ANDNOT) at scale → RoaringBitmap is the standard choice today. Sequential/long-run bitmaps (columnar/analytics indexes) → EWAH-style compression tends to win. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
