Seeking optimization advice

[Dave]

Hello all,

I have written an expression interpreter, and a profiler has told me that a
specific part of it is in need of optimization. My purpose in posting to
this newsgroup is to solicit suggestions on how I might accomplish my
intended aim more efficiently.

My interpreter supports the "if-then-else" construct. In addition, it
supports variables, which means it has a symbol table. As you probably
suspect, the symbol table is implemented using std::map<std::string,
var_value_t>.

Currently, the processing of an if-then-else proceeds as follows:

1. Save the original symbol table state; say the returned handle to the
saved state is 1

2. Parse the boolean condition and store the result in rval (note that it is
not possible for the symbol table to be altered here; I do not allow
assignment in the condition of an if-then-else)

3. Parse the "then" subexpression

4. Save the "then" symbol table state; say the returned handle to the saved
state is 2

5. Restore symbol table state 1

6. Parse the "else" subexpression

7. Save the "else" symbol table state; say the returned handle to the saved
state is 3

8. If rval is true, restore symbol table state 2, else restore symbol table
state 3


The following serves as an example expression to which this processing could
be applied (assume 'a' is an integer initialized to 0):

if true then a := 6 else a := 7

Note that the "then" and "else" subexpressions can be arbitrarily complex;
they might even be another if-then-else. And so on recursively... This
fact eliminates some potential shortcuts.

What needs to be optimized is the saving and restoring of the symbol table
states. Currently, states are saved in a std::vector<>. When state is
requested to be saved, I just push_back() the whole symbol table and return
the index as the "handle" to the saved state. When the restoration of a
state is requested, I just index the std::vector<> with the passed handle
(index) and copy back the symbol table at that index. All of this copying
of std::map<> is taking a big toll performance-wise.

I have already tried adding an undo / redo feature that allows me to operate
only upon the actual symbol table itself. Unfortunately, I quickly
discovered that this is not robust enough. State is not properly
maintained. A careful run through of the example expression above
demonstrates this.

Can anybody suggest something more efficient than my current implementation?
It is a requirement that whatever I implement remain within the realm of
standard C++.

Thank you,
Dave

 

[Claudio Puviani]

I have written an expression interpreter, and a
profiler has told me that a specific part of it is
in need of optimization.

Smart profiler. Mine just tells me the relative execution times
of various parts of my code. ;-)

My purpose in posting to this newsgroup is to
solicit suggestions on how I might accomplish my
intended aim more efficiently.

My interpreter supports the "if-then-else" construct.
In addition, it supports variables, which means it has
a symbol table. As you probably suspect, the symbol
table is implemented using std::map<std::string, var_value_t>.

And here's your first chance at an optimization: a hash table
would be quite a bit faster, especially for large symbol tables.
It's not by chance that most compilers and interpreters use hash
tables for their symbol tables. If your particular implementation
of the standard library doesn't include a hash_map (which is
universally believed to be slated for adoption in the next
standard), you can:

a) use STLport
b) use the Dinkumware Standard C++ Library
c) use any available implementation of a hash table
d) roll your own (hash tables are actually among the most trivial
of data structures)

Currently, the processing of an if-then-else proceeds as follows:

1. Save the original symbol table state; say the returned handle
to the saved state is 1

2. Parse the boolean condition and store the result in rval (note
that it is not possible for the symbol table to be altered here; I
do not allow assignment in the condition of an if-then-else)

3. Parse the "then" subexpression

4. Save the "then" symbol table state; say the returned handle
to the saved state is 2

5. Restore symbol table state 1

6. Parse the "else" subexpression

7. Save the "else" symbol table state; say the returned handle
to the saved state is 3

8. If rval is true, restore symbol table state 2, else restore
symbol table state 3

You'd save yourself a lot of trouble if you decoupled the parsing
from the semantic analysis. If you did, you wouldn't need to save
various states of your symbol table (very time consuming) and you
could skip over the 'then' or 'else' clauses depending on the
evaluation of the condition without impacting the symbol table or
any other program state.

What needs to be optimized is the saving and restoring
of the symbol table states.

No, it needs to be eliminated.

Can anybody suggest something more efficient than
my current implementation?
Done.

It is a requirement that whatever I implement remain
within the realm of standard C++.

Nothing that I suggested departs in any way from the C++ standard
(the standard does NOT preclude using data structures other than
the standard containers), so you're all set.

Claudio Puviani

 

[David Harmon]

On Tue, 13 Apr 2004 09:05:21 -0700 in comp.lang.c++, "Dave"

What needs to be optimized is the saving and restoring of the symbol table
states. Currently, states are saved in a std::vector<>. When state is
requested to be saved, I just push_back() the whole symbol table and return

All that building and copying of your entire symbol table undoubtedly
consumes a lot of time, no matter how you might try to optimize it.

As Claudio suggests, you may eventually end up decoupling the parsing
from the semantic analysis by building a expression tree while parsing,
then traversing the tree to execute. That would allow you to skip the
unexecuted subexpressions with a single test.

Maybe a smaller step would be to have a state flag, executing versus
skipping. While skipping, nothing could be stored in your symbol table
and while not skipping everything proceeds as before. The flag would be
set based on the 'if' condition.