Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign

I need some benchmarks for the codecompletion, any volunteers?

<< < (2/2)

Ceniza:
About 2.8 seconds.

Pentium 4 3.0GHz HT. Windows XP.

rickg22:
Ceniza: Maybe in Linux you don't see that effect, but I see it on windows all the time (the scrollbar 'growing'). Must be implementations difference.

Thanks for the info guys, I just wanted to confirm something. The class browser is built in the main thread on windows. This explains the sudden pause during the tree construction (you can't move the window, press any key, etc).

Anyway, I did some benchmarks of my own, and I think I found the cause for the slow construction of the tree. This is what I got with the codeblocks_rick.cbp and the help plugin, and for both:


--- Quote ---[03:25:45.796]: Updating class browser...
[03:25:48.750]: Class browser updated (682 nodes added in 234955 search operations).
[03:30:38.484]: Class browser updated (5 nodes added in 36 search operations).
[03:31:45.625]: Class browser updated (682 nodes added in 238395 search operations).

--- End quote ---

and it's no coincidence that 234955 =~ 682^2 / 2. It's the 1 + 2 + ... N formula discovered by Gauss. In other words, it means that the tree construction takes quadratic complexity.

Where? The tree construction is based on a routine called "AddNodeIfNotThere". It searches ALL the nodes to see if there's anyone matching the current token name. And this happens for all nodes added. So at first it searches for one node, then two, three, etc. So the number of operations done to add the whole tree are: 1 + 2 + 3 + ... N.

I made an experiment. I removed the search and added all the nodes to the tree (even if there were duplicates). The tree was constructed around at least 4 times faster!! (It shouldn't surprise us, without checks the tree is constructed in linear time).

Currently I'm optimizing the algorithm to do a binary search instead a linear search, this will cut the searches from O(N^2) to O(N log(N)).

Ceniza:
It seems to be more of a Windows problem then. I just tried the same thing on that P4 using Kubuntu Feisty and it's about as instantaneous as it's here. It takes perhaps ~0.2 seconds in that P4, and no "growing" effect either.

pauliusz:
~1 second on Windows 2000 SP4, Athlon XP 2500+, 512MB RAM, CB rev 4238, wx284.

rickg22:
OK I tested with build 4238... the addition of nodes seems very fast. HOWEVER...

I did the following experiment. I closed the root node, and opened it again. IMMEDIATELY i switched to the files, and tried to press the DOWN key. I couldn't do anything for... 1.47 seconds.

OK, guys, I got all the data I needed. Thank you for your cooperation :)

Navigation

[0] Message Index

[*] Previous page