EggData - a grave performance problem! (BUG)

hi there,

earlier this week i posted a snippset for creating motion path and lines ->

while it works really nice for small set’s of data i ran into a serious issue. the more points you throw in , the slower it gets, and it slows down EXPONENTIALLY.

first, adding vertex data slows down, that’d be the myCurve.addVertex(i) dall. up to around 2000 it’S really fast, then it starts to noticably slow down and around 10k it’s only like 1k per second.
while 2k points loaded in 0.18 seconds. 20k took 27seconds.

the real deal-breaker is this one NodePath(loadEggData(
when loading 2k vertices it completes in 0.6 seconds. increasing it to 20k vertices it takes 114 seconds!

loading the same ammount of data in one piece is more than hundret time slower than loading the same ammount of data but in 10 smaller pieces. is there a reason for this? a bug maybe?


Ah, that’s probably the O(n^2) operation in EggPrimitive::test_vref_integrity(). That is to say, it’s an algorithm that takes k * n * n operations to complete, where k is some constant and n is the number of vertices. So, it behaves fine where n is small, but takes exponentially longer as n increases.

It’s never caused us trouble before, because most primitives are polygons, which rarely have more than a handful of vertices. Curves, of course, are primitives as well; but I guess most of our curves rarely had more than a few dozen vertices tops (more complicated NURBS curves than that are uncommon, except in unlucky cases like yours, I guess).

The good news is that this is just a debug function anyway and can be safely commented out without causing problems. So, if you’re willing to build your own Panda, you can solve this just by commenting out the call to test_vref_integrity() wherever it occurs, or by inserting a return statement at the front of that function.

I’ll put in a better, more long-term fix. My apologies for the troubles.


well i figured i did rare stuff with it :stuck_out_tongue: thanks a lot for confirming and providing a workaround :slight_smile: