[alsa-devel] [PATCH 1/2 v2] ASoC: soc-cache: block based rbtree compression

[Takashi Iwai]

At Mon,  2 May 2011 13:28:28 +0100,
Dimitris Papastamos wrote:
> 
> This patch prepares the ground for the actual rbtree optimization patch
> which will save a pointer to the last accessed register block that was used
> in either the read() or write() functions.
> 
> Each node manages a block of up to RBTREE_BLOCK_NUM registers.  There can be
> no two nodes with overlapping blocks.  Currently there is no check in the code
> to scream in case that ever happens.  Each block has a base and top register,
> all others lie in between these registers.  Note that variable length blocks
> aren't supported.  So if you have an interval [8, 15] and only some of those
> registers actually exist on the device, the block will have the non-existent
> registers as zero.  There is also no way of reporting that any of those
> non-existent registers were accessed/modified.
> 
> The larger the block size, the more probable it is that one of the
> managed registers is non-zero, and therefore the node will need to be
> allocated at initialization time and waste space.
> 
> If register N is accessed and it is not part of any of the current
> blocks in the rbtree, a new node is created with a base register
> which is floor(N / RBTREE_BLOCK_NUM) * RBTREE_BLOCK_NUM and a top
> register as base_register + RBTREE_BLOCK_NUM - 1.  All other registers
> in the block are initialized as expected and the node is inserted into
> the tree.
> 
> Signed-off-by: Dimitris Papastamos <dp at opensource.wolfsonmicro.com>

Looking through the patch, I wonder whether it gives a performance
gain enough for the additional complexity.  Did you measure somehow?


thanks,

Takashi