search

arximboldi / immer

Postmodern immutable and persistent data structures for C++ — value semantics at scale
https://sinusoid.es/immer
Boost Software License 1.0
2.5k stars 181 forks source link

comparison with phil nash's hamts? #23

Closed jjl closed 6 years ago

jjl commented 6 years ago

Hi,

They published Phil Nash's HAMT talk from cppcon yesterday on youtube. His talk notes page has a link to immer, so I'm guessing you talked :) My question is how immer's HAMTs compare to phil's, broadly. I saw from the talk there are a few optimisations he's missing (some of which he even mentions), but is there anywhere his HAMT has the edge over immer's? if so, let's steal ideas!

arximboldi commented 6 years ago

They published Phil Nash's HAMT talk from cppcon yesterday on youtube. His talk notes page has a link to immer, so I'm guessing you talked :) My question is how immer's HAMTs compare to phil's, broadly. I saw from the talk there are a few optimisations he's missing (some of which he even mentions), but is there anywhere his HAMT has the edge over immer's? if so, let's steal ideas!

Nice! Phil does a great job in his presentations---I did attend his HAMT session at CppNow which was very eloquent and clear. We had also a chat about the topic at CppCon.

As he mentioned, I do implement an optimization (the CHAMP variation of the HAMT structure) which stores the values at one level of the tree in a contiguous block, enabling less indirection, more cache locallity, and also has less branching during iteration---at the cost of one extra bitmap lookup step during search, but the other advantages compensate. With CHAMP also inequeal trees can always be found in log time, even if the do not share structure. CHAMP stores one extra bitmap, but on 64 bit architectures it does not add extra memory usage (it is packed in the same word with the other bitmap).

I keep following Phil's work. Neither of us has implemented transients yet... [1] if he gets to it before me I am sure his implementation will be again a good source of insight and inspiration.

There were links to benchmarks and papers in the CHAMP pull request here: https://github.com/arximboldi/immer/pull/19

[1] I am busy with work and... preparing a mini-Redux-for-C++ library to show at MeetingCpp... I know, the clock is freacking ticking!

-- ∿∿∿ https://sinusoid.al ∿∿∿ https://sinusoid.es

jjl commented 6 years ago

Brilliant, thanks for the summary. And I'd love a link to your redux lib when you're done :)

arximboldi commented 6 years ago

@jjl I just realized when reviewing the issues: here is the Redux lib https://github.com/arximboldi/lager and here is a talk about it: https://www.youtube.com/watch?v=NMol_5-2owo