SegmentCache

[cehteh]

WIP! caching segments should improve performance considerably. integration and benching follows.

[cehteh]

On 2023-06-10 12:31, Jacob Ryan McCollum wrote:

@mccolljr commented on this pull request.

Looks quite nice so far. Just a couple thoughts based on a first pass

+#[cfg(test)]
fn checked_log2_floor(v: usize) -> Option {

If this is no longer used by the implementation, it is okay to remove it and the associated test.

Things are somewhat in flux still. I was thinking about keeping code for now and eventually do some 'cleanup'. Would be nice to use cargo-mutants to improve testing in future, but that's not my goal right now.

• /// Called by ctors to assert that the configuration is valid.

• ///
• /// Some MemConfig implementations may put constraints on (const generic)
• /// parameters. Currently it is impossible to assert these at compile time in stable
• /// rust. In debug builds we check these constraints when a SegVec uses some
• /// config. The three shipped MemConfig implementations check here that the 'FACTOR' is
• /// not zero.
• fn debug_assert_config();

I think there are some stable ways to assert things about const generics now.

This is one example (stolen from a thread in an issue on static_assertions):

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=98221c637c7195f1fc530cc51d3848f8

If you feel up to it, I think it would be better to have these assertions happen at compile time... especially given that the (current) assertions are simple, just checking the FACTOR value against 0.

I didn't know that such works. lets see about adding that later. Note that I left the road open for user implementations of MemConfig. Dunno if everything can be asserted. The debug-only test at runtime as it is currently should be good enough anyway.

My priority is to get it usable (with the cache thing if possible) and have performance in the same Ballpark than std Vec (somewhat slower is to be expected of course).

Plan is to improve and help maintaining my bits in future, but for now I just want to get it going and work on something else (the thing where I need SegVec).

-- Reply to this email directly or view it on GitHub: https://github.com/mccolljr/segvec/pull/20#pullrequestreview-1473477867 You are receiving this because you authored the thread.

Message ID: @.***>

[cehteh]

I updated the benchmarks (not committed yet) and want to share some observations:

1. https://public.pipapo.org/segvec_bench/criterion/push%20values/report/index.html These push() 100k values.

• In most cases we are less than 2x slower than std Vec which is pretty good
• Linear<1> is insanely slow, disabled that in the benchmark.
• Linear<1024> is the fastest.
• The Proportional math is very expensive.
• Caches work but the gains at push() are marginal except for the odd Proportional case. Still slower than Linear<1024>

2. https://public.pipapo.org/segvec_bench/criterion/access_ordered/report/index.html This is just a loop calling get(0..N)

   • std Vec is significantly faster
   • Linear<1024> is fastest because of the simplest math
   • Not cached SegVec is more than a magnitude slower than std Vec
   • Caching works well but is slower than Linear<1024>

3. https://public.pipapo.org/segvec_bench/criterion/access_semirandom/report/index.html This is get(index) where index is randomly modified to +/-500

   • SegVec with default (Exponential<1>) is more than 3 times slower than Vec
   • Caching improves it considerably
   • Linear<1024> is still faster than the cached Exponential<1>

4. https://public.pipapo.org/segvec_bench/criterion/access_random/report/index.html This is totally random access

   • SegVec with defaults performs bad
   • Caching is even worse (not surprising)
   • Linear<1024> is close to the std Vec and pretty fast

Conclusion

Proportional is too slow, needs better math, maybe something that is only 'roughly' proportional (I have no actual idea about that).

While the caching idea works, it's gains are not as big as I hoped for and it is always outperformed by Linear<1024>.

I will scrap the SegmentCache.

• For speed use 'Linear<BIGFACTOR>'.
• When memory is scare then use 'Exponential<MODESTFACTOR>'
• Don't use 'Proportional' unless it becomes improved. (scrap it too?)

https://public.pipapo.org/segvec_bench/criterion/report/

[cehteh]

This might closed now, the code exists as proof-of-concept. It could be reasonable to revive this idea when (cacheable) fast indexing on Proportional or Exponential is required. Still chosing Linear would likely be the better approach.