This is an archive of the discontinued LLVM Phabricator instance.

Make the bloom filter a bit larger.
ClosedPublic

Authored by ruiu on Jan 17 2018, 3:21 PM.

Details

Summary

I created https://reviews.llvm.org/D42202 to see how large the bloom
filter should be. With that patch, I tested various bloom filter sizes
with the following commands:

$ cmake -GNinja -DCMAKE_BUILD_TYPE=Debug -DLLVM_ENABLE_LLD=true \
  -DLLVM_ENABLE_PROJECTS='clang;lld' -DBUILD_SHARED_LIBS=ON \
  -DCMAKE_SHARED_LINKER_FLAGS=-Wl,-bloom-filter-bits=<some integer> \
  ../llvm-project/llvm
$ rm -f $(find . -name \*.so.7.0.0svn)
$ ninja lld
$ LD_BIND_NOW=1 perf stat bin/ld.lld

Here is the result:

-bloom-filter-bits=8   0.220351609 seconds
-bloom-filter-bits=10  0.217146597 seconds
-bloom-filter-bits=12  0.206870826 seconds
-bloom-filter-bits=16  0.209456312 seconds
-bloom-filter-bits=32  0.195092075 seconds

Currently we allocate 8 bits for a symbol, but according to the above
result, that number is not optimal. Even though the numbers follow the
diminishing return rule, the point where a marginal improvement becomes
too small is not -bloom-filter-bits=8 but 12. So this patch sets it to 12.

Event Timeline

ruiu created this revision.Jan 17 2018, 3:21 PM

I also observed that increasing of filter size gives boost.
And wiki says:
"A Bloom filter with 1 % error and an optimal value of k, in contrast, requires only about 9.6 bits per element, regardless of the size of the elements. This advantage comes partly from its compactness, inherited from arrays, and partly from its probabilistic nature. The 1 % false-positive rate can be reduced by a factor of ten by adding only about 4.8 bits per element."
So I think value = 12 is probably should be fine balance.

Patch increases size of output though and orthogonal to other possible optimizations (like attemps to tweak Shift2). Are we ok to increase output size atm ?

This revision was not accepted when it landed; it landed in state Needs Review.Jan 19 2018, 3:58 PM
This revision was automatically updated to reflect the committed changes.