Optimize IdList by Using an Index and a Proper Iterator

[ruevs]

This drastically speeds up IdList operations. Closes #932 and #939 and even the remainder of #841.
It is similar to #992 and Evil-Spirit@44eb1a4

It optimizes IdList by Using an Index and a Proper Iterator:

• Use std::vector<T> elemstore to store elements. Avoids manual memory management.
• Add an index (std::vector<int> elemidx) that avoids moving large objects when adding elements.
• Add a free element list (std::vector<int> freelist) that speeds up element removal by avoiding rearranging the element storage. It also avoids reallocations when adding elements later.
• Add a proper iterator. It will be used to remove NextAfter - which is a performance bottleneck.
• Use range-based for loops Instead of NextAfter for all IdList objects this resolves a performance regression of iteration being O(n*log n) rather than O(n).

[vespakoen]

I am really happy that this is being worked on, and I tested it out and it really improved speed a lot for complex things.

I did get some warnings when compiling this (this is one of many but they all look like the same thing in different places):

In file included from /Users/koen/Projects/solvespace/src/modify.cpp:8:
In file included from /Users/koen/Projects/solvespace/src/solvespace.h:149:
/Users/koen/Projects/solvespace/src/dsc.h:449:46: warning: field 'list' will be initialized after field 'position'
      [-Wreorder-ctor]
        iterator(IdList<T, H> *l, int pos) : list(l), position(pos) {
                                             ^
/Users/koen/Projects/solvespace/src/dsc.h:549:51: note: in instantiation of member function
      'SolveSpace::IdList<SolveSpace::Request, SolveSpace::hRequest>::iterator::iterator' requested here
    iterator end() { return IsEmpty() ? nullptr : iterator(this, elemidx.size()); }
                                                  ^
/Users/koen/Projects/solvespace/src/modify.cpp:269:17: note: in instantiation of member function
      'SolveSpace::IdList<SolveSpace::Request, SolveSpace::hRequest>::end' requested here
    for(auto &r : SK.request) {
                ^

I cannot make any other comments to the code since it is way above my head.

In short, it works over here! =)

[ruevs]

I am really happy that this is being worked on, and I tested it out and it really improved speed a lot for complex things.

Thanks for taking a look!

I did get some warnings when compiling this (this is one of many but they all look like the same thing in different places):

In file included from /Users/koen/Projects/solvespace/src/modify.cpp:8:
In file included from /Users/koen/Projects/solvespace/src/solvespace.h:149:
/Users/koen/Projects/solvespace/src/dsc.h:449:46: warning: field 'list' will be initialized after field 'position'
      [-Wreorder-ctor]
        iterator(IdList<T, H> *l, int pos) : list(l), position(pos) {

Hmm yes this is an obscure one: https://stackoverflow.com/questions/1828037/whats-the-point-of-g-wreorder
I fixed it and force pushed, but have no gcc on this machine to try it. It does not show up in the Ubuntu log of the CI. Please check if it is fixed.

[vespakoen]

Yup that fixed those warnings!

I think it should probably have shown up in the macOS logs (I got those with clang on macOS at least)

[phkahler]

So is this "better" than #992? Are either of them complete? I haven't been following this since it wasn't going in 3.0.

[ruevs]

I think it is a bit cleaner than #992 since it uses std:vector. It is also ever so slightly faster (see here #992 (comment)) probably because I have a freelist that makes removal of elements faster.

It is complete. The tests pass. It would be nice if a few people do a code review and run the address sanitizers on Linux. When I get to my other system I will try on Windows with clang and sanitizers as well.

I did try adding an extra std::unordered_map to map between handles and indexes to speed up search from O(log(n)) but it did not make an overall speed difference in the tests I tried. It just shifted which functions are on the the critical path. But this can always be added later.

[phkahler]

Is this a win over #992 then? I'd like to settle on one of these soon.

[ruevs]

Is this a win over #992 then?

By definition I'm biased ;-) Others should review both.

[phkahler]

Merging this version. Let's get some real usage to test it. I'm a bit concerned about bugs, but there's not much reason for people to be running edge builds right now.