search

lacuna / bifurcan

functional, durable data structures
MIT License
967 stars 51 forks source link

Avoid loop iterations in Map intersection #7

Closed fehrenbach closed 6 years ago

fehrenbach commented 6 years ago

I was reading your code, because my own CHAMP set operations were a huge mess of nested conditionals. I stole your switch idea and the trick of iterating only over set bits. Thanks!

Anyway, I noticed that you could skip more bits in the intersection, instead of iterating over them and then doing nothing. I removed the redundant cases too. This might be a stylistic thing, though. Or maybe it should be assert false;?

A similar trick should apply for difference. And there might be similar code in IntMaps etc., I haven't checked.

(Also, I haven't tested this. I might have misunderstood something and it's wrong, or just slower.)

ztellman commented 6 years ago

Thanks for catching this. I'm not sure if this will make things noticeably faster, but I can't see why it'd be slower. The redundant cases didn't serve any purpose, I was just making sure I didn't forget any cases during the initial dev process and then didn't clean it up afterwards.