In article <3D8### [at] freefr>,
 Nicolas Calimet <pov### [at] freefr> wrote:

> 	Do you mean that the current POV-Ray parser (which I never
> really investigated) searches the full list of keywords to get the
> proper token ? If so, what about hash tables as used when parsing
> mesh triangles/textures ?

No, I don't mean this. I was talking about a hypothetical way of doing 
it, not a way to modify the current POV-Ray code.


> 	Putting the last resolved symbol at the beginning of the
> list assumes a high probability to find the same symbol again.

Not really...if it isn't used again, it quickly moves back "behind" the 
more often used keywords. The more often resolved ones spend more time 
at the front of the list, where they are hit more quickly. It is kind of 
like using the front of the list as a cache, it is extremely simple and 
much faster overall than just going through the list.


> I agree this is good for such big objects as meshes (and usually a 
> very big scene is made of very big meshes...). But I don't think it's 
> better than using hash tables in general. [A perfect hash table would 
> be appropriate for build-in keywords which number is fixed].

For the POV-Ray parser, it is probably the fastest way. Sapphire 
identifiers are pointers to strings: all identifiers with the same 
string point to the same memory location, so comparison is fast, and 
symbols are stored in a linked list, so it is extremely fast to remove 
an element and push it on at the front of the list.
It would be possible to use a hash table, and it might be faster, but it 
would use more memory and the number of symbols in a table is usualy too 
small to get a real benefit. For POV, the requirements are different, 
and a hash table is probably the best way.

I might eventually use a hash table for the compiler part of Sapphire, 
it currently does a string comparison against every built-in token until 
it finds a match. Compile times are already fast enough that I don't 
even notice the delay, though.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message