[syslog-ng] [PATCH] value-pairs: Add value_pairs_foreach_sorted().

[Gergely Nagy]

Balazs Scheidler <bazsi at balabit.hu> writes:

[...]
> This is uberslow.

Indeed, it is.

> - iterates over the hash table: O(n), plus a lot of allocations (GList)
> - sorts the list (O(logN)
> - iterates the list and then at each iteration it looks up the Nth
> element of the list: O(N*N)
> - for each iteration does a hash lookup: O(logN)
>
> I would love to use a different data structure that keeps keys/data in
> sorted form instead of a hash table, that might be faster than a
> hashtable in the first place and could be sorted regardless of the
> value-pairs invocation.
>
> What do you think?

I agree, will try to think of something sensible during the holidays.

-- 
|8]