Engineering Faster Sorters for Small Sets of Items

[renox]

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]

Perhaps it's worth considering succinct data structures (https://en.wikipedia.org/wiki/Succinct_data_structure), e.g.:

- BitMagic: http://bitmagic.io/, https://github.com/tlk00/BitMagic

- Succinct Data Structure Library 2.0: https://github.com/simongog/sdsl-lite, https://github.com/simongog/sdsl-lite/wiki/Literature

[jdoerfert]

Does this sound interesting: http://llvm.org/docs/ProgrammersManual.html#llvm-adt-indexed... http://llvm.org/doxygen/IndexedMap_8h_source.html

[thedance]

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]

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.

[Upvoter33]

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