kdelibs/kdecore

[Eray Ozkural]

CVS commit by exa: 

Optimize the template array class with dynamic size used in netwm
for consecutive appends, a la open table. If you allocate twice the
size of the table in near-the-last cases the amortized access time
becomes O(1) instead of O(N) which is generally regarded as a good
thing. That's why all vector implementations expand or shrink the
array by a factor of 2, rather than simply assuming the new size.

I don't know what Qt is doing with arrays but I'd assume it ought to be OK.
I will be looking at misc. data structure use/implementation throughout kdelibs
and other modules. There are many potential venues of optimizations in
this respect, and all significant optimizations come from change of algorithm
as you all know. (Meaning nothing else is significant) Also see
kdevelop/lib/structure

I tested this small change but reviews are welcome.

CCMAIL: kde-optimize@kde.org


  M +9 -7      netwm.cpp   1.85


--- kdelibs/kdecore/netwm.cpp  #1.84:1.85
@@ -475,5 +475,7 @@ Z &NETRArray<Z>::operator[](int index) {
     } else if (index >= sz) {
         // allocate space for the new data
-        Z *newdata = new Z[index + 1];
+        // open table has amortized O(1) access time
+        // when N elements appended -- exa
+        Z *newdata = new Z[max(2 * sz, index+1)];
 
         // move the old data into the new array