Numbers of a tree :P

[hendu]

I was bored, reading the irr code, and the {mesh,texture}caches looked inefficient.

Especially the add-search-sort combo, as done on both getmesh and addtexture, looked fatal.

So, I replaced the irrArray in meshcache with a red-black tree Addition slowed down about 5x, other operations gained. The add-search one gained a ton.
Though, nobody runs with this many meshes/textures, so even the loading time impact would be low in real scenarios.

Enjoy some thursday night geek porn:

Tree numbers:

Doing 1000 test rounds. Numbers in usecs.

Adding meshes: 8583
Searching: 4217
Deleting: 3831
Add-search cycles: 9179

Doing 1000 test rounds. Numbers in usecs.

Adding meshes: 15098
Searching: 4635
Deleting: 3818
Add-search cycles: 9105

Doing 1000 test rounds. Numbers in usecs.

Adding meshes: 11399
Searching: 4190
Deleting: 3849
Add-search cycles: 9048


Avg add: 11693 5.1
Avg search: 4347 0.65
Avg del: 3832 0.04
Avg a-s: 9110 0.007


Irr numbers:

Avg add: 2263
Avg search: 6613
Avg del: 89593
Avg a-s: 1260000



Doing 1000 test rounds. Numbers in usecs.

Adding meshes: 2256
Searching: 6155
Deleting: 86203
Add-search cycles: 1259400

Doing 1000 test rounds. Numbers in usecs.

Adding meshes: 2268
Searching: 7114
Deleting: 86568
Add-search cycles: 1264028

Doing 1000 test rounds. Numbers in usecs.

Adding meshes: 2267
Searching: 6570
Deleting: 96009
Add-search cycles: 1260852

[hybrid]

Do you have some code (for changes and test)?

[hendu]

Sure, here's the benchmark app:

http://pastebin.ca/2087525

cpp Code: Select all

#include <irrlicht/irrlicht.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
 
using namespace irr;
using namespace scene;
using namespace video;
 
static struct timeval tick;
 
static void settime() {
        gettimeofday(&tick, NULL);
}
 
static void gettime() {
        struct timeval tmp;
        gettimeofday(&tmp, NULL);
 
        int usec = (tmp.tv_sec - tick.tv_sec) * 1000000;
        usec += (tmp.tv_usec - tick.tv_usec);
 
        printf("%d\n", usec);
 
        settime();
}
 
 
int main(int argc, char **argv) {
 
        IrrlichtDevice *dev = createDevice(EDT_NULL);
        IMeshCache *c = dev->getSceneManager()->getMeshCache();
        IAnimatedMesh *t, *m = dev->getSceneManager()->addArrowMesh("first");
        t = m;
 
        unsigned int rounds = 10000, i;
        char name[10];
 
        if (argv[1]) rounds = atoi(argv[1]);
 
        printf("\n\tDoing %u test rounds. Numbers in usecs.\n\n", rounds);
 
        printf("Adding meshes: ");
        settime();
        for (i = 0; i < rounds; i++) {
                sprintf(name, "%u", i);
                c->addMesh(name, m);
        }
        gettime();
 
        printf("Searching: ");
        for (i = 0; i < rounds*2; i+=2) {
                sprintf(name, "%u", i);
                c->getMeshByName(name);
        }
        gettime();
 
        printf("Deleting: ");
        for (i = 0; i < rounds; i++) {
                sprintf(name, "%u", i);
                m = c->getMeshByName(name);
                c->removeMesh(m);
        }
        gettime();
 
        m = t;
        printf("Add-search cycles: ");
        for (i = 0; i < rounds; i++) {
                sprintf(name, "%u", i);
                c->addMesh(name, m);
                c->getMeshByName(name);
        }
        gettime();
 
 
 
        dev->drop();
        return 0;
}

As for the implementation itself, it's not quite production quality yet In the usual case the improvement would be measured in milliseconds, and I would have to remove the *index* methods. Those expose the internal array structure, and can't be implemented on top of a binary tree.

If those are ok, I can finish it and replace the texture cache too.

[hybrid]

Well, if we change the deletion scheme to become lots faster we could probably even stay with the original system as it seems. Removing existing methods is usually not a good idea. In this case, though, it's probably much better to have a fast deletion that to have the index methods. For me, they are anyway just used to quickly remove meshes. See the irony!?
I hope you benchmarked release versions.

[hendu]

Well, if we change the deletion scheme to become lots faster we could probably even stay with the original system as it seems.

Delete is not the biggest pain point, it's the unnecessary sorts. If you load 10 meshes, the array is sorted 9 times, 8 too many.
Since searching is the most used operation, done on both add, delete, and by itself, it makes sense to use a balanced tree.


The numbers above are from slightly patched 1.7.2.

For the index methods, they aren't used anywhere inside irrlicht, and the docs advice against using them in user code - the index may point to the wrong thing after sort/addition/deletion.

[hendu]

Haha, I had finished things and _then_ noticed there already was an implementation of the r-b tree in there. Mine was 1/5th of the LOC, but will rebase on top of the irrmap.

[hendu]

Patches posted:
https://sourceforge.net/tracker/?func=d ... tid=540678

[hendu]

Ping.

I admit the patch could've been split into four - removing index methods, adding SNamedPath equality operator, and replacing the two caches - but I hope it's not too big to be reviewed as is.

[hybrid]

Well, what do you expect? Don't count on it being integrated into Irrlicht 1.8. We have a bunch of other patches waiting as well.

[hendu]

Honest comments on the line of "it sucks", or "too invasive for this cycle"

[hybrid]

It has too many changes to include it directly, but it's interesting to play around with this one and see what we will do with it.

[hendu]

Adding that we've been using this for a few months without any downsides.

[hybrid]

Yeah, but as I said, there's too much hassle with this to get it into 1.8. We have far too many things already now which need fixing.

[hendu]

Sorry, I meant that for the other viewers, in case they wanted to try it themselves.