[retroforth] Re: Speed up of 'find' word
- From: "Helmar Wodtke" <helmwo@xxxxxx>
- To: retroforth@xxxxxxxxxxxxx
- Date: Tue, 25 Jan 2005 18:43:20 +0100
retroforth@xxxxxxxxxxxxx schrieb am 25.01.05 18:29:41:
>
>
> On Tue, January 25, 2005 9:20, Helmar Wodtke said:
> > retroforth@xxxxxxxxxxxxx schrieb am 25.01.05 18:03:29:
> > Hi Ron,
> >
> > another idea for speed up the linear search in dictionary for FORTH
> > programs,
> > is to keep track of the position that linked to the found entry in
> > dictionary
> > and remove the found entry from dictionary and put it on the top of the
> > dictionary.
>
> This would be a big speed increase in the usual case (after a word has been
> found) but would slow down programs which don't exhibit locality.
>
> It would also be a little tricky to implement, one would have to take care to
> fix up pointers properly...
Wait, it means fixing up 3 positions in memory for each found word ("last" or
the link of first word, link of previous word and link of found word), if the
found word is not the first. The register renaming to trace position of
previous word should not take much time (in fact it should take no time at
all). A huger program has probably some hundreds of words. So the searching of
occurrences of "dup" allone takes much more time than that simple fixups. Also
you could do optimizations in a way that a word is moved to top only if it's
later than 10 elements from top. I've implemented such a strategie some years
ago and it improved the speed very, very much. Try it if you dont believe. I
came back from this optimization at the moment I used a good hashing for my
dictionary. Well, at the moment I do linear search only (but at the moment I
also want to implement a simple system that's able to be extended).
Bis dann,
Helmar
-- Binary/unsupported file stripped by Ecartis --
-- Type: application/x-pkcs7-signature
-- File: smime.p7s
-- Desc: S/MIME Cryptographic Signature
Other related posts:
