I remember there was some discussion a while back about speeding up
parsing of commands. Hash tables for sure were discussed, don't remember
what else.
What about using binary space trees?
For those who aren't fimiliar with them, a BSP tree is a series of nodes,
each containing a link to two "children": one "lesser" in value than the
node, and one "greater" in value than the node. Making a balanced BSP
tree is quite easy once you've found the "average" value to work from.
Even partially unbalanced trees can still be quite fast.
A sample BSP tree diagram:
"Hello"
/ \
"Goodbye" "Hola"
/ \ / \
"Adios" "Greetings" "Hi" "Salute"
\ / \
"Bye" "Later" "See ya"
If this were a linked list, it would take on avg 5 strcmp()s to find the
correct node. But as a linked list, it takes no MORE than 4. Obviously
its a speed increase.
I'm probably going to sit down and do it, for the hell of it... anything
that saves me a couple cycles is worth it ('specially when I have like
150 commands and 200 socials).
The time savings could really add up eventually. With 350 total
commands, thats about 18.75 strcmp()s avg to parse out any command,
instead of the otherwise 175 strcmps. Thats nearly 9 times faster to
parse out commands. Take an average of 4 commands parsed per pulse bineg
sent on a decent mud, thats a total of 625 strcmp()s saved... for 62500
strcmp()s per second
(unless Im wrong on the assumption that CircleMUD processes input every
pulse, 10 pulses a second).
Or am I just wasting my time, and the savings isn't really worth the
extra code? (albeit however little extra code it would take)
- Chris Jacobson
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST