[retroforth] Re: Speed up of 'find' word
- From: "Helmar Wodtke" <helmwo@xxxxxx>
- To: retroforth@xxxxxxxxxxxxx
- Date: Tue, 25 Jan 2005 18:20:28 +0100
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. So often used words occur earlier in search process. The meaning of
the order in dictionary is not changed (since there can not be a word of same
name found before the word that was actually found...). This conceptual change
will speed up processing a much more, since usual FORTH programs have a kind of
"locality" of used words. Eg. a new defined word will not be used very often
later and so they do not need to be searched in first place (say, before
"dup"). The major disadvantage is that a programmer that is used to see the
words in same order as definitions is confused a little at the first moment.
Bis dann,
Helmar
>
> 'find' currently only does a full check of the word if it's the same length as
> the word sought. This is good; but it can be further sped up by only doing
> the rep cmpsb if the first char is the same. This prevents a lot of push/pop
> and the cmpsb:
>
>
> ; trashes EDX
> code 'find', find ;
> push ebx ;
> mov ebx, flast ;
> .o: push ecx ;
> upop ecx ;
> ; get first char to do quick compare:
> mov dl, byte [eax]
> .a: mov ebx,[ebx] ;
> or ebx,ebx ;
> jz .end ;
> cmp cl,[ebx+8] ;
> jne .a ;
> ; same length; compare first char
> cmp dl, [ebx+9]
> jne .a
> .len: push esi ; same length
> push edi ;
> push ecx ;
> mov esi,eax ;
> lea edi,[ebx+9] ;
> rep cmpsb ;
> pop ecx ;
> pop edi ;
> pop esi ;
> jne .a ;
> mov eax,[ebx+4] ; exact match
> clc ;
> jmp .ret ;
> .end: upsh ecx ; no matches
> stc ;
> .ret: pop ecx ;
> pop ebx ;
> next
>
>
>
>
> --
> My GPG public key is at http://ronware.org/
> fingerprint: 8130 734C 69A3 6542 0853 CB42 3ECF 9259 AD29 415D
>
>
>
>
-- Binary/unsupported file stripped by Ecartis --
-- Type: application/x-pkcs7-signature
-- File: smime.p7s
-- Desc: S/MIME Cryptographic Signature
Other related posts:
