tdf#109097 - mdds accelerating random lookups

[Michael Meeks]

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 at collabora.com <><, Pseudo Engineer, itinerant idiot