uClibc++ associative_base performance

[Asier Llano Palacios]

Quick performance analysis. I think I'm maybe biassed by the tests I've
been performing, but I'd like to contribute a performance bump to uClibc
++, and I'd like to know your point of view.

Current performance situtation
==============================
Timing:
uClibc++-0.2.1: My test spent 9 seconds.
uClibc++-0.2.2: My test spent 1 minutes and 30 seconds (aprox).
Target time: Less than 1 second.

General analysis:
After some profiling I realized that most of the time is spent in
std::map operations. In 0.2.1 the time is spent in the std::map::insert
operation, and in uClibc++-0.2.2 the time is mostly spent in the
std::map::find operation.

Performance by operation:
Having a look at the algorithms used in the associative containers in
uClibc++ I've been looking which operations are not scalable. We will
have a look at the media of the timing spent for each operation as a
function of the number of elements in the collection.
uClibc++-0.2.1:
  find    = O(log(n))  <--- Binary search (fast)
  insert  = O(n)       <--- Binary search, but linear storage (slow)
  iterate = O(1)
uClibc++-0.2.2:
  find    = O(n)  <-- Linear search (very slow)
  insert  = O(n)  <-- Linear search to insert (because of the find)
  iterate = O(1)

What I'd like to contribute
===========================
I'd like to contribute a performance improvement in every associative
container by improving the associative_base. This way the set, mset, map
and mmap. I'll try to implement it so that it still passes the same
number of tests with the following timing:
  find    = O(log(n))  <-- binary search in a tree
  insert  = O(log(n))  <-- binary search, tree bouncing.
  iterate = O(1)       <-- walking in a tree (it will be slower than
                           the previous but will not grow with n).

Of course, I wan't to mantain:
  - Small code, small binary size and small memory footprint
  - Iterators point to the same position even after element insertion
    and deletion.

You'll have news about this implementation as soon as I finish it.

Licensing
=========
The only thing I don't like about uClibc++ is its LGPL license, its
quite restrictive to me. I work for an enterprise where I develop and
contribute all the general purpose code (the code that is not specific
for our application). I consider myself a community contributor. I use
uClibc++ and I have other application specific libraries (that I don't
see the point of sharing them, because they are too specific of our
embedded architecture). Even if I contribute the other libraries I
wouldn't contribute them under LGPL. While mantaining the source code
like it is now, I would like to build the uClibc++ and my specific
libraries in one shared library to make the binary size of the code
smaller (having only one "general purpose for me" shared library). I've
tested it and I could gain some binary size by joining both libraries
compilation. I think that I cannot join LGPL and other binary code in a
single library. Is there any possibility to have a less restrictive
license (like X11 or BSD)?. I don't want to fork, nor sell uClibc++, I
only want to have linking flexibility with uClibc++ and some non LGPL
code.

Thank you, 
Asier 
 
----------------------------------------- PLEASE NOTE -------------------------------------------
This message, along with any attachments, may be confidential or legally privileged. 
It is intended only for the named person(s), who is/are the only authorized recipients.
If this message has reached you in error, kindly destroy it without review and notify the sender immediately.
Thank you for your help.
µSysCom uses virus scanning software but excludes any liability for viruses contained in any attachment.
 
------------------------------------ ROGAMOS LEA ESTE TEXTO -------------------------------
Este mensaje y sus anexos pueden contener información confidencial y/o con derecho legal. 
Está dirigido únicamente a la/s persona/s o entidad/es reseñadas como único destinatario autorizado.
Si este mensaje le hubiera llegado por error, por favor elimínelo sin revisarlo ni reenviarlo y notifíquelo inmediatamente al remitente. Gracias por su colaboración.  
µSysCom utiliza software antivirus, pero no se hace responsable de los virus contenidos en los ficheros anexos.