Re: tdf#109097 - mdds accelerating random lookups

Hi there,

On 27/08/17 07:28, Noel Grandin wrote:
> One relatively simple thing that might be worth trying is simply moving
> the block_size member out of the block and into it's own std::vector.

        Multi-type-vector has:

    struct block
    {
        size_type m_size;
        element_block_type* mp_data; ...
    }

    typedef std::vector<block*> blocks_type;

        Which is interesting;

> That will make the search vastly more friendly to the cache and memory
> subsystem, and will probably give you between 4x and 10x speedup on
> large spreadsheets, depending on the CPU in use.

        Not entirely convinced here - -but- I expect that dropping one
indirection eg.

        typedef std::vector<block> blocks_type;

        rather than that extra indirection should significantly improve cache
locality for iteration.

        Kohei - does having that extra indirection help with the implementation
of iterators ? I assume that transferring the mp_data pointer as well as
the size is much the same as transferring a block* ?

        Also from a perf. perspective - if we have to shuffle, move chunks of
the pointer vector down, and we remove the pointer chasing / scattered
accesses there - I suspect we can get the re-numbering almost for free
at the same time for insert/delete.

        Regards,

                Michael.

-- 
michael.meeks@collabora.com <><, Pseudo Engineer, itinerant idiot