[syslog-ng] [PATCH (3.4) 0/2] value-pairs: Efficient sorting

[Gergely Nagy]

Gergely Nagy <algernon at balabit.hu> writes:

> In the two patches that will follow, a subtle, yet very important
> change will be made to the core of value-pairs: instead of building a
> GHashTable during a value_pairs_foreach(), we now build a binary tree,
> that's sorted at insert time, and traversing through it is much
> faster.
>
> This also buys us sorted keys almost free of charge!

Just did a quick benchmark, and bombarded both the current value-pairs
and the GTree version with logs on 10 connections, outputting JSON to a
file. The results are very close, within the margin of error, but the
GTree version won by about 300 msg/sec more (which is about 0.7% of an
increase).

There's one other thing I want to do: the ValuePairs structure currently
has a GHashTable for the explicitly specified key=value pairs. I will
try to turn that into a pointer array instead. This has the advantage of
being a lot more efficient than a hash table, with the downside that we
allow dups (but due to the sorting, only the latest entry will be used,
but all others will be evaluated too). I believe that such dups are
going to be reasonably rare, so the performance hit this causes will be
outweighted by the performance gain we get from dropping GHashTable.

-- 
|8]