Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #41225 > unrolled thread

dictionary layouts

Back to article view | Back to comp.lang.forth

Contents

  dictionary layouts Mat <dambere@web.de> - 2015-08-09 04:39 -0700
    dictionary layouts Mark Wills <markwills1970@gmail.com> - 2015-08-09 11:37 -0700
      Re: dictionary layouts Mat <dambere@web.de> - 2015-08-09 12:30 -0700
    Re: dictionary layouts anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-08-10 08:05 +0000
      Re: dictionary layouts Mat <dambere@web.de> - 2015-08-10 03:57 -0700
      Re: dictionary layouts hughaguilar96@gmail.com - 2015-08-10 15:00 -0700
        Re: dictionary layouts Mat <dambere@web.de> - 2015-08-11 14:15 -0700

#41225 — dictionary layouts

Hello,

I'm thinking about advantages and disadvantages of different dictionary layouts. Important for me is thereby the relation between simplicity, memory usage and search performance. In this regard, I've noticed that by efficient factoring, the last defined words are often temporary the most frequent used ones. If so, probably the memory overhead for hashed dictionaries if avoidable though a simple cache which list pointers to the most frequent used words for example. This cache can be combined with either a traditional linked list or a balanced binary tree (which I would prefer) as layout.

I think such dictionary concept can probably be a good compromise between search performance and memory usage.

What are the experiences with hashed dictionaries or tree based ones? have someone implemented both strategies ?

Mat.

[toc] | [next] | [standalone]

#41227

In my experience dictionary search performance had never been a problem. My system runs on a 16 bit TMS9900 at 3mhz. FIND is coded in assembler. I've had literally hundreds of words in the dictionary ( > 500 ) and never noticed a problem. It's just a simple,  classical linked list. 

There may be other reasons to take a different approach,  in my experience dictionary search speed wasn't one of them.

[toc] | [prev] | [next] | [standalone]

#41229

Am Sonntag, 9. August 2015 20:37:04 UTC+2 schrieb Mark Wills:
> In my experience dictionary search performance had never been a problem. My system runs on a 16 bit TMS9900 at 3mhz. FIND is coded in assembler. I've had literally hundreds of words in the dictionary ( > 500 ) and never noticed a problem. It's just a simple,  classical linked list. 
> 
> There may be other reasons to take a different approach,  in my experience dictionary search speed wasn't one of them.

I have take a look at your TurboForth and think it is a nice programming environment for the ti99/4a. However my system is somewhat more different in using tags for different data formats. Because the same word declaration can exist for different tags, I organize them in separate dictionaries to ease parsing. However the total number of word declarations can get very large this way.

[toc] | [prev] | [next] | [standalone]

#41252

Mat <dambere@web.de> writes:
>In this regard, I've noticed that by efficient=
> factoring, the last defined words are often temporary the most frequent us=
>ed ones. If so, probably the memory overhead for hashed dictionaries if avo=
>idable though a simple cache which list pointers to the most frequent used =
>words for example. This cache can be combined with either a traditional lin=
>ked list or a balanced binary tree (which I would prefer) as layout.
>
>I think such dictionary concept can probably be a good compromise between s=
>earch performance and memory usage.

No, it's worse in search performance, memory usage, and implementation
complexity.  Given the requirements of the Forth dictionary, hashing
with external chaining is hard to beat (especially if you don't
implement FORGET, but also if you do).  It's only slightly more
complex than a linked list, and uses only h-1 (where h is the number
of hash buckets) more memory, and improves search time by a factor of
h when the word is not found (because it is a number), and a little
less than h when the word is found.

In contrast, your cache consumes memory, too, and *increases* the
search time if the word is not found.  If you use hashing for your
cache, the overall code complexity is at least as bad as for a hashed
dictionary; if you use a balanced binary tree for your cache, the
complexity is even worse, and the access speed is slower than for a
hashed cache; if you use linear search through your cache, the
performance is slow.

Using a binary tree for the dictionary with n entries consumes n
additional cells compared to a linked list.  If I use that much extra
memory for hashing, e.g., external chaining with n hash buckets, the
average chain length is 1 and hashing is really fast.

Using a balanced binary tree has the same memory overhead, but is even
more complex to implement.  One particular problem is that, in Forth,
you can have the same name several times in the dictionary, and always
need to find the one that was inserted last.  I can see how to do that
with (unbalanced) binary trees (can you), but for balanced binary
trees that's non-trivial (unless you keep only the last entry in the
tree, but that costs another cell in each entry for the link to the
previous definition with the same name).

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2015: http://www.mpeforth.com/euroforth2015/euroforth2015.htm

[toc] | [prev] | [next] | [standalone]

#41258

Am Montag, 10. August 2015 10:34:44 UTC+2 schrieb Anton Ertl:
> >In this regard, I've noticed that by efficient=
> > factoring, the last defined words are often temporary the most frequent us=
> >ed ones. If so, probably the memory overhead for hashed dictionaries if avo=
> >idable though a simple cache which list pointers to the most frequent used =
> >words for example. This cache can be combined with either a traditional lin=
> >ked list or a balanced binary tree (which I would prefer) as layout.
> >
> >I think such dictionary concept can probably be a good compromise between s=
> >earch performance and memory usage.
> 
> No, it's worse in search performance, memory usage, and implementation
> complexity.  Given the requirements of the Forth dictionary, hashing
> with external chaining is hard to beat (especially if you don't
> implement FORGET, but also if you do).  It's only slightly more
> complex than a linked list, and uses only h-1 (where h is the number
> of hash buckets) more memory, and improves search time by a factor of
> h when the word is not found (because it is a number), and a little
> less than h when the word is found.
> 
> In contrast, your cache consumes memory, too, and *increases* the
> search time if the word is not found.  If you use hashing for your
> cache, the overall code complexity is at least as bad as for a hashed
> dictionary; if you use a balanced binary tree for your cache, the
> complexity is even worse, and the access speed is slower than for a
> hashed cache; if you use linear search through your cache, the
> performance is slow.
> 
> Using a binary tree for the dictionary with n entries consumes n
> additional cells compared to a linked list.  If I use that much extra
> memory for hashing, e.g., external chaining with n hash buckets, the
> average chain length is 1 and hashing is really fast.
> 
> Using a balanced binary tree has the same memory overhead, but is even
> more complex to implement.  One particular problem is that, in Forth,
> you can have the same name several times in the dictionary, and always
> need to find the one that was inserted last.  I can see how to do that
> with (unbalanced) binary trees (can you), but for balanced binary
> trees that's non-trivial (unless you keep only the last entry in the
> tree, but that costs another cell in each entry for the link to the
> previous definition with the same name).
> 
> - anton
> -- 
> M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
> comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
>      New standard: http://www.forth200x.org/forth200x.html
>    EuroForth 2015: http://www.mpeforth.com/euroforth2015/euroforth2015.htm

Thanks. After rethinking the approach and some testing I came to the same conclusion. What I had not thought in particular, is the memory overhead for tree structures in combination with the implications of multiple word definitions so your explanation was very helpful for me. I'm now implement hashed dictionaries after founding a simple way to reduce there memory overhead.

[toc] | [prev] | [next] | [standalone]

#41264

On Monday, August 10, 2015 at 1:34:44 AM UTC-7, Anton Ertl wrote:
> Mat <dambere@web.de> writes:
> >In this regard, I've noticed that by efficient=
> > factoring, the last defined words are often temporary the most frequent us=
> >ed ones. If so, probably the memory overhead for hashed dictionaries if avo=
> >idable though a simple cache which list pointers to the most frequent used =
> >words for example. This cache can be combined with either a traditional lin=
> >ked list or a balanced binary tree (which I would prefer) as layout.
> >
> >I think such dictionary concept can probably be a good compromise between s=
> >earch performance and memory usage.
> 
> No, it's worse in search performance, memory usage, and implementation
> complexity.  Given the requirements of the Forth dictionary, hashing
> with external chaining is hard to beat (especially if you don't
> implement FORGET, but also if you do).  It's only slightly more
> complex than a linked list, and uses only h-1 (where h is the number
> of hash buckets) more memory, and improves search time by a factor of
> h when the word is not found (because it is a number), and a little
> less than h when the word is found.
> 
> In contrast, your cache consumes memory, too, and *increases* the
> search time if the word is not found.  If you use hashing for your
> cache, the overall code complexity is at least as bad as for a hashed
> dictionary; if you use a balanced binary tree for your cache, the
> complexity is even worse, and the access speed is slower than for a
> hashed cache; if you use linear search through your cache, the
> performance is slow.
> 
> Using a binary tree for the dictionary with n entries consumes n
> additional cells compared to a linked list.  If I use that much extra
> memory for hashing, e.g., external chaining with n hash buckets, the
> average chain length is 1 and hashing is really fast.
> 
> Using a balanced binary tree has the same memory overhead, but is even
> more complex to implement.  One particular problem is that, in Forth,
> you can have the same name several times in the dictionary, and always
> need to find the one that was inserted last.  I can see how to do that
> with (unbalanced) binary trees (can you), but for balanced binary
> trees that's non-trivial (unless you keep only the last entry in the
> tree, but that costs another cell in each entry for the link to the
> previous definition with the same name).

I have Symtab in the novice package: http://www.forth.org/novice.html

It is not a self-balancing tree --- it moves the more commonly accessed nodes toward the root of the tree (for example, DUP is typically more common than ROT and everything is more common than BYE) --- it also does some balancing at the leaves because the commonality of the nodes isn't all that important at that low-level in the search.

Symtab uses the same amount of memory as a hash table assuming that the hash-table is rebuilt when it is half full. Symtab has the advantage that it grows smoothly --- unlike a hash-table, there is no pause for it to be rebuilt when the size crosses an arbitrary threshold --- with a hash-table the user has to predict ahead of time how big the dictionary will be in order to not have it get rebuilt because it is too small while yet not wasting memory because it is too big. 

Your "cache" sounds like a Splay Tree --- I don't like this idea because it assumes that words will be accessed again soon after they have been accessed in the past, but there is no reason to believe that this is true (for example, why would DUP be used shortly after it was already used?) --- by comparison, my Symtab keeps track of the words overall frequency of access (for example, DUP is overall used quite often compared to other words). My symtab does insert new words into the root of the tree rather than the leaves, and then let them descend down to their appropriate level --- this takes into account the idea that newly defined words will be used soon after they are defined, which is generally true --- many words are only used soon after they are defined, and then never used again, in which case they start at the root and then sink like a rock to a leaf.

Symtab has been discussed here: https://groups.google.com/forum/#!topic/comp.lang.forth/w3tHPsTaZvE
Actually, "discuss" isn't a very good term --- I was told that it "sucks" and is "crap," and then Elizabeth Rather denounced me for being homophobic when I complained about this language.

[toc] | [prev] | [next] | [standalone]

#41292

Am Dienstag, 11. August 2015 00:00:19 UTC+2 schrieb hughag...@gmail.com:
> Your "cache" sounds like a Splay Tree --- I don't like this idea because it
> assumes that words will be accessed again soon after they have been accessed in 
> the past, but there is no reason to believe that this is true (for example,
> why would DUP be used shortly after it was already used?)
Yes is was basically a Splay Tree. Of course, for a language like Forth my initial assumption is obvious wrong. However, the language I have in mind is not related to any Forth standard. In comparison is is quite different to Forth. For example there exist no stack shuffling words like dup, drop or over. Instead stack loads are done though indexing into a stack (so values are pushed to a stack but the stack itself is addressed like an array where loaded elements are copied to the top-of-stack position). Because this functionality is an inherent part of the parser (beside other functionality which is implemented though word definitions in Forth, if at all) there exist barely functions which are independent of there definition position.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web