5 ms·

Engineering Faster Sorters for Small Sets of Items

38 points by matt_d 7y ago

Upvoter33 7y ago
Love papers like this, hyper-focused on a fun problem and then full of hacks.
thedance 7y ago
The most interesting thing to me is "the compiler reduces its optimizations with increasing compilation effort, when compiling only a single source file." Is this GCC-specific, or does it also hold for clang? And can it be tuned away?
- jdoerfert 7y ago
  Clang will not "reduce compilation effort" and I do not believe GCC does that. There are heuristics that look at things like function size but I don't think that is what they mean. Generally speaking, translation units are independent if you do not run link-time-optimizations (LTO) and optimizations follow a (basically) predetermined order which might be influence by the input but not by the amount of work done.
  - thedance 7y ago
    I’ve never heard of or experienced gcc using some kind of cost model for compilation time, either. With all these huge protobuf-generated files you’d think I would have noticed if it existed.
deleted 7y ago
[deleted]
renox 7y ago
In the similar topic, I'm trying to find maps optimised for a small maximum number of items (8 or 16) indexed by integers. Curiously I failed to find discussions about this topic.. But std::map seems very badly fit for this kind of map.
- matt_d 7y ago
  Perhaps it's worth considering succinct data structures (https://en.wikipedia.org/wiki/Succinct_data_structure https://en.wikipedia.org/wiki/Succinct_data_structure), e.g.: - BitMagic: http://bitmagic.io/ http://bitmagic.io/, https://github.com/tlk00/BitMagic https://github.com/tlk00/BitMagic - Succinct Data Structure Library 2.0: https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite, https://github.com/simongog/sdsl-lite/wiki/Literature https://github.com/simongog/sdsl-lite/wiki/Literature
  - renox 7y ago
    Thanks but these structures are size optimised, I'm looking for CPU usage optimised structures.
- jdoerfert 7y ago
  Does this sound interesting: http://llvm.org/docs/ProgrammersManual.html#llvm-adt-indexedmap-h http://llvm.org/docs/ProgrammersManual.html#llvm-adt-indexed... http://llvm.org/doxygen/IndexedMap_8h_source.html http://llvm.org/doxygen/IndexedMap_8h_source.html
  - renox 7y ago
    I will have a look thanks. I think I'll implement it with two arrays one for keys one for values and a loop to find the key index, then return the corresponding value It may be better to fully unroll the loop, I'll have to benchmark this. SSE may be interesting too.

38 points by matt_d 7y ago

Love papers like this, hyper-focused on a fun problem and then full of hacks.

The most interesting thing to me is "the compiler reduces its optimizations with increasing compilation effort, when compiling only a single source file." Is this GCC-specific, or does it also hold for clang? And can it be tuned away?

jdoerfert 7y ago
Clang will not "reduce compilation effort" and I do not believe GCC does that. There are heuristics that look at things like function size but I don't think that is what they mean. Generally speaking, translation units are independent if you do not run link-time-optimizations (LTO) and optimizations follow a (basically) predetermined order which might be influence by the input but not by the amount of work done.
- thedance 7y ago
  I’ve never heard of or experienced gcc using some kind of cost model for compilation time, either. With all these huge protobuf-generated files you’d think I would have noticed if it existed.

deleted 7y ago

[deleted]

renox 7y ago

In the similar topic, I'm trying to find maps optimised for a small maximum number of items (8 or 16) indexed by integers. Curiously I failed to find discussions about this topic.. But std::map seems very badly fit for this kind of map.

matt_d 7y ago
Perhaps it's worth considering succinct data structures (https://en.wikipedia.org/wiki/Succinct_data_structure https://en.wikipedia.org/wiki/Succinct_data_structure), e.g.: - BitMagic: http://bitmagic.io/ http://bitmagic.io/, https://github.com/tlk00/BitMagic https://github.com/tlk00/BitMagic - Succinct Data Structure Library 2.0: https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite, https://github.com/simongog/sdsl-lite/wiki/Literature https://github.com/simongog/sdsl-lite/wiki/Literature
- renox 7y ago
  Thanks but these structures are size optimised, I'm looking for CPU usage optimised structures.
jdoerfert 7y ago
Does this sound interesting: http://llvm.org/docs/ProgrammersManual.html#llvm-adt-indexedmap-h http://llvm.org/docs/ProgrammersManual.html#llvm-adt-indexed... http://llvm.org/doxygen/IndexedMap_8h_source.html http://llvm.org/doxygen/IndexedMap_8h_source.html
- renox 7y ago
  I will have a look thanks. I think I'll implement it with two arrays one for keys one for values and a loop to find the key index, then return the corresponding value It may be better to fully unroll the loop, I'll have to benchmark this. SSE may be interesting too.