On Windows we can use PeekMessageA().

On macOS we can use [NSApp nextEventMatchingMask:...].

On GTK our only option is to manually pump the events while, most likely, grabbing the keyboard/mouse events so that they don't arrive to our widgets and cause reentrancy issues. Paint events will still have to be blocked explicitly. It's ugly.

This might not be worth exploring after profiling my slow SolveSpace operations revealed it's really just the IdList class implementation scaling poorly.

Evil-Spirit's IdList changes at https://github.com/Evil-Spirit/solvespace-master/tree/id-list-indexing made an enormous usability difference with my large assemblies, though there seemed to be some bugs to work out.

@vcaputo That List is a critical piece used all over SolveSpace. If it can be made faster that's good, but I think those changes should not impact the usage in other areas of the code - see the changes in the second patch where simple indexing with elem[i] is replaced with double indirection elem[something[i].something]. If that's necessary in file saving I'm wondering if it's needed any number of other places too. @Evil-Spirit do you consider that "done" or is it proof of concept? Do you think it would be good to overload the [] operator instead of requiring changes outside the list itself?

@phkahler There's no doubt @Evil-Spirit's changes as-is have some brokenness, but they at least serve as a PoC highlighting a severe bottleneck when it comes to working with large assemblies.

SolveSpace regularly becomes unusably slow when my assemblies cross a certain complexity threshold, it has severely restricted the design space I'm able to access with this otherwise awesome tool in a very real sense. Experimenting with such assemblies using @Evil-Spirit's hack immediately frees me to continue working with them in ways previously impossible, until an assert throws :).

I'm fairly sure the current implementation of IdList causes some assembly operations to become quadratic, which explains the drastic difference in performance @vcaputo is observing.

So looking at the code... SShell::MakeFromAssemblyOf() is simple except for copying all the curves from both shells and assigning new IDs to them. That means every curve in the resultant shell will cause a call to AddAndAssignId() So far that seems like all linear work (and it should be) but...

    H AddAndAssignId(T *t) {
        t->h.v = (MaximumId() + 1);
        Add(t);

        return t->h;
    }

And then in Add we have:

    void Add(T *t) {
        AllocForOneMore();

        // Look to see if we already have something with the same handle value.
        ssassert(FindByIdNoOops(t->h) == nullptr, "Handle isn't unique");

        // Copy-construct at the end of the list.
        new(&elem[n]) T(*t);
        ++n;
        // The item we just added is trivially sorted, so "merge"
        std::inplace_merge(begin(), end() - 1, end(), Compare());
    }

And searching on the inplace_merge we find:
https://en.cppreference.com/w/cpp/algorithm/inplace_merge
With the relevant part being in complexity, which is linear - and that makes assembly quadratic.

I'm not sure the inplace_merge is needed in general, but in the case of AddAndAssignID() it is not. The Id in that case is guaranteed to be greater than all the others in the list, so just appending the new item is enough.

@vcaputo since you have an assembly that exhibits the problem could you try copying the content of Add() into AddAndAssignID() except for the inplace_merge() call at the end and see if that helps? This should reduce the assembly operation to linear time instead of quadratic.

There are many things in SolveSpace with quadratic time complexity or worse, so this might just help things by a constant factor rather than making it amazingly better.

Or just try this:
https://github.com/phkahler/solvespace/tree/speed

It reduced another problematic model time to generate by 10 percent, but that's not an assembly.

@phkahler I tried your branch, it's a minor improvement over master, but insignificant in terms of moving the complexity threshold where things become unusable.

@Evil-Spirit's changes are transformative in this regard.

I've uploaded a simple reproducer assembly here:

https://pengaru.com/~vc/tmp/solvespace-repro (core-half.slvs is the top-level assembly)

That's an extreme example. I'm mostly doing more architectural work like framing small homes/sheds/roofs etc. But the assembly style is similar, the reproducer just has a much higher number of step-repeats compared to a bunch of framed walls or roof rafters.

With @Evil-Spirit's changes the repro loads in a couple seconds and things stay interactive. It's kind of amazing considering when I last worked on that assembly I had given up after waiting an eternity for SolveSpace to produce core-half.slvs. It still needed the other half of core layers in the empty gaps rotated 90 degrees, but I had to abandon modeling the idea at the time due to the unusable performance.

I was just experimenting with some reworked Evil-Spirit IdList changes rebased atop master, and there's been a bunch of buggy behaviors that I was assuming were caused by them.

But it turns out some of these bugs I see on plain master, if I'm patient enough for it to try work with these assemblies. This led me to picking some arbitrary older commit to find some point where these bugs weren't present, and happened to choose 9253e5f because it builds with my gtkmm version, in the hopes that I could try rebasing the IdList changes on that and maybe find a happy medium.

Not only did I find the bugs I was experiencing gone, everything was much faster than master is, even without the IdList changes. Not fast enough for loading the repro core-half.slvs in under a minute or anything, but interactivity with architectural assemblies is substantially better. So it looks like there's been some significant performance regressions between 9253e5f and master, in addition to other bugs unrelated to this particular topic.

I'll be creating another issue for one of them shortly.

@vcaputo you might also look at 2 open pull requests related to the lists. I think #429 and #433.

@vcaputo
@phkahler
@whitequark
I've commented inside my commint about IdList indexing.

@phkahler

see the changes in the second patch where simple indexing with elem[i] is replaced with double indirection elem[something[i].something]. If that's necessary in file saving I'm wondering if it's needed any number of other places too.

This changes is only necessary to make testing system save/load file round trip happy for an old files. Can be just ignored.

@phkahler

see the changes in the second patch where simple indexing with elem[i] is replaced with double indirection elem[something[i].something]. If that's necessary in file saving I'm wondering if it's needed any number of other places too.

This changes is only necessary to make testing system save/load file round trip happy for an old files. Can be just ignored.

@Evil-Spirit File compatibility is important, but if that's all those changes are needed for then we will not have to make similar changes throughout the code, which is what I was worried about.

Is it correct that those changes improve performance by allowing sorting and moving to be done on a list of much smaller objects (almost pointers) rather than moving large objects around? Much more cache friendly.

@phkahler yes, exactly. That's because of more cache coherence during binary search, and small amount of moved/reallocated data which causes a lowering of complexity for almost all algorithms conatined adding/removing of idlist elements. Please, read more comments inside my original commit (I've mentioned you)

Since the IdList was the main topic of this issue I am giving the links to the pull requests that have since improved it comparably to the original code by EvilSpirit:
#1002
#973

In addition Eigen is now in (in 3.1):
#1159

@vcaputo have you tried version 3.1 - you seem to have quite a few big/heavy models.

@ruevs I would much rather continue addressing performance issues than add this capability (at this time).

@phkahler absolutely! In my opinion the original topic needs to be closed. So I'll close this.

But since the conversation here veered in the direction of performance in general and the (now solved) IdList bottleneck, and @vcaputo seems to use SolveSpave for some complicated things I thought of asking him how 3.1 works on them.