3 ms·

There's an incredibly simple algorithm for such an access pattern. Store all values in a vector, without regards for order. Then when an element is requested, f

There's an incredibly simple algorithm for such an access pattern. Store all values in a vector, without regards for order. Then when an element is requested, find it's index i with a linear scan and swap elements i and i/2. In an access pattern where the same elements are requested over and over this very quickly brings those elements to the front, giving really fast access times. This super simple data structure would totally blow the rest out of the water on this benchmark, and should illustrate the issue with it quite well.

jnordwick 10y ago
Reminds me of the tricks self-balancing trees do, rotating the most accessed elements towards the root.
- pacaro 10y ago
  In particular splay trees do this by rotating elements to the top whenever they are accessed (IIRC) and while they aren't formally balanced, they tend to be "balanced enough" -- if you only ever access a few elements, they will be clustered at the top and the structure of the rest of the tree doesn't matter
  - jnordwick 10y ago
    We've done few variations of those for representing parts of a trading book where you often have a few price points (the inside) are hit more often and their performance is more important. Self-balancing data structures are very cool.
user5994461 10y ago
And enable OpenMP afterwards, to process the 1 million strings in parallel using all the available cores.
- R_haterade 10y ago
  I'm learning Omp right now, and I'm excited about it, but my sarcasm filter is off today--are you serious about this? What about the inability to exit a parallel region--I was under the impression that once you start a parallel for, you can't exit it until it's run through the entire iteration.
- KayEss 10y ago
  I hate it when libraries try this sort of thing. I've already used all of the cores higher up in the program logic where it's far more effective, but doing that all the library is going to achieve is a net slow down of all throughput. Don't blindly throw work at multiple cores low down in algorithms. Amdahl's law tells you that the pay off is likely low, and if the program already makes proper use of the cores you're just going to slow things down.
  - user5994461 10y ago
    Agreed that library needs to think about how programs will interact with them. That program is just a benchmark to map millions of string to integers, it's valid to optimize processing.

jnordwick 10y ago

Reminds me of the tricks self-balancing trees do, rotating the most accessed elements towards the root.

pacaro 10y ago
In particular splay trees do this by rotating elements to the top whenever they are accessed (IIRC) and while they aren't formally balanced, they tend to be "balanced enough" -- if you only ever access a few elements, they will be clustered at the top and the structure of the rest of the tree doesn't matter
- jnordwick 10y ago
  We've done few variations of those for representing parts of a trading book where you often have a few price points (the inside) are hit more often and their performance is more important. Self-balancing data structures are very cool.

user5994461 10y ago

And enable OpenMP afterwards, to process the 1 million strings in parallel using all the available cores.

R_haterade 10y ago
I'm learning Omp right now, and I'm excited about it, but my sarcasm filter is off today--are you serious about this? What about the inability to exit a parallel region--I was under the impression that once you start a parallel for, you can't exit it until it's run through the entire iteration.
KayEss 10y ago
I hate it when libraries try this sort of thing. I've already used all of the cores higher up in the program logic where it's far more effective, but doing that all the library is going to achieve is a net slow down of all throughput. Don't blindly throw work at multiple cores low down in algorithms. Amdahl's law tells you that the pay off is likely low, and if the program already makes proper use of the cores you're just going to slow things down.
- user5994461 10y ago
  Agreed that library needs to think about how programs will interact with them. That program is just a benchmark to map millions of string to integers, it's valid to optimize processing.