[SLOF] [PATCH slof v3 5/5] fdt: Pass the resulting device tree to QEMU

[Segher Boessenkool]

Hi Alexey,

On Fri, Oct 06, 2017 at 12:40:49PM +1100, Alexey Kardashevskiy wrote:
> On 05/10/17 23:21, Segher Boessenkool wrote:
> > On Thu, Oct 05, 2017 at 06:39:03PM +1100, Alexey Kardashevskiy wrote:
> >> btw 336ms now (was 351ms), nice. See "[PATCH slof v4 2/3] fdt: Pass the
> >> resulting device tree to QEMU" commit log for all numbers.
> > 
> > Nice indeed :-)
> > 
> > If you want further speedups, a juicy target is improving how the
> > wordlists are searched, since that will help everything.
> 
> I was pretty happy with 1.7sec really :) With fdt, I would stop now and
> probably come back later to look at wordlists when/if you answer my
> questions 3 mails above in this thread.

Good plan :-)  (I hope I can find that mail, if not, just ping me?)

> And is there much to improve just search? I'd think the linked list needs
> to be replaced with something sorted so it is a different data structure.

You still need something like a linked list because there can be two
words in the same wordlist with the same name, and you can still find
both in some ways, but the normal ways always should find the newer.

The current scheme to accelerate lookup is very simplistic: it takes a
hash of the word name, and has a cache indexed by that.  The cache has
just one way (no chaining, no nothing), so two conflicting names will
keep fighting for the slot.  If something is not found in the cache,
the slow way (walked the linked lists) is used.

The whole cache is blown away whenever the search order is changed,
etc., too.

As you see it could all be a lot faster (at the cost of complexity).
It always was fast enough ;-)

Some ways things could be improved:
* Keep caches per word list, not just one globally.
* Actually reorder the word lists when a word is found, i.e. pull a
found word closer to the word list head; but you also need to maintain
the original order some way, for words like MARKER or FORGET.


Segher