This set of changes greatly reduces the number of string operations
we perform when parsing an expression and when looking up variables.
It does this by two means:
1) identify functions already in the scanner and distinguish them by
token (and not by the full name) afterwards
2) record all identifiers encountered, always return the same
(unique) pointer for the same identifier, and store only pointers
instead of copying the string. This allows us to avoid copies and
to compare strings for equality with a simple pointer comparison.
The unique identifier database contains a pre-populated and sorted
table with most of the predefined names, with search time O(M*log N)
where M is the average length of an identifier and N the number of
identifiers. Anything new gets added to a linear list with the usual
O(M*N) search time. Since user-defined identifiers should be
relatively uncommon, this is probably not a big performance loss.
A few optimizations are still possible, e.g., smarter handling of
operators (which now go into the "user-defined identifiers" pile),
and some identifiers are still missing in the table. But the basic
concept is there.
- Werner
Werner Almesberger (11):
libfpvm: make scanner aware of function names and handle arity in
parser
parser.y: move node allocation and initialization to shared function
libfpvm: pass token in struct ast_node
fpvm.c: use token instead of operator name in operator2opcode
fpvm.c: use token instead of operator name in "compile"
libfpvm: infrastructure for efficient unique ID pointers
libfpvm: use unique strings in interface between scanner and parser
libfpvm: convert constants already in fpvm_parse
libfpvm: copy only pointer to identifier into AST, not the entire
string
libfpvm: copy only pointer into bindings, not the entire string
fpvm.c: use unique strings also in fpvm_assign ... and bring in the
harvest
software/include/fpvm/fpvm.h | 4 +-
software/libfpvm/Makefile | 13 ++-
software/libfpvm/ast.h | 11 ++-
software/libfpvm/fnp.ids | 193 ++++++++++++++++++++++++++++++++++++++
software/libfpvm/fpvm.c | 186 ++++++++++++++++++++----------------
software/libfpvm/idgen | 57 +++++++++++
software/libfpvm/parser.y | 130 ++++++++++++-------------
software/libfpvm/parser_helper.c | 12 ++-
software/libfpvm/scanner.h | 10 +-
software/libfpvm/scanner.re | 84 ++++++++++++-----
software/libfpvm/subdir.mak | 13 ++-
software/libfpvm/unique.c | 169 +++++++++++++++++++++++++++++++++
software/libfpvm/unique.h | 18 ++++
13 files changed, 705 insertions(+), 195 deletions(-)
create mode 100644 software/libfpvm/fnp.ids
create mode 100755 software/libfpvm/idgen
create mode 100644 software/libfpvm/unique.c
create mode 100644 software/libfpvm/unique.h
_______________________________________________
http://lists.milkymist.org/listinfo.cgi/devel-milkymist.org
IRC: #milkymist@Freenode
