Re: [Qemu-devel] [RFC 15/38] radix-tree: add generic lockless radix tree module

[Emilio G. Cota]

On Thu, Sep 10, 2015 at 15:25:50 +0100, Alex Bennée wrote:
> 
> Emilio G. Cota <address@hidden> writes:
> 
> > This will be used by atomic instruction emulation code.
> 
> If we are adding utility functions into the code base like this (which I
> can see being useful) we should at least add some documentation with
> example calling conventions to docs/

Ack.

> Have you any performance numbers comparing the efficiency of the radix
> approach to a "dumb" implementation?

I tried a few lazy solutions (meaning having to write less code, which
isn't that dumb), such as having a g_hash_table protected by a mutex. But
this means potential contention on that mutex, so that's not a better option.

Whatever the solution might be, this is a slow path (only invoked
on atomic ops or regular stores that affect lines previously accessed
with atomic ops) so scalability is a more important goal than absolute speed.

The big perf impact comes on x86 when instrumenting stores, which is
orthogonal to this; invoking a helper on each store is a huge perf
killer for some benchmarks. It's OK for others though, but I still think
we should be able to do better.

Thanks,

                Emilio