Jump to content
  • Advertisement
Sign in to follow this  
BrickInTheWall

Need some tips to optimize my code...

This topic is 3163 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi guys, I've built an expression parser a week or two ago to perform mathematical operations by implementing the shunting-yard-algorithm. But instead of converting to RPN I evaluate immediately. You don't really have to understand how the algorithm works, the problems with my implementation are quite obvious. I finished what I had started, but now I want to port the code to a microcontroller to build a simple calculator (to make more use of it than just a boring Windows App). Here is the function that implements the algorithm found at http://en.wikipedia.org/wiki/Shunting-yard_algorithm :
double EvaluateExpression(char* inputString)
{
	stack<double> operandStack;
	stack<Token> operatorStack;
	char token;
	Token lastToken = Void;
	Token currentToken = Void;

	for (int i = 0; !(inputString == '\0'); i++)
	{
		token = inputString;

		// If token is a number, push it onto the operandStack.
		if (IsNumber(token))
		{
			currentToken = Number;

			operandStack.push(ExtractNumber(inputString, &i));
		}

		if (IsFunction(inputString, i))
		{
			currentToken = GetFunctionType(inputString, &i);
			operatorStack.push(currentToken);
		}

		// If the token is an operator, check the operatorStack.
		if (IsOperator(token))
		{
			currentToken = GetOperatorType(token, lastToken);
			
			// Is there an operator at the top? IMPORTANT: Parenthesis are excluded here!
			// You can't compare two unary or a unary to a binary operator in terms of associativity.
			while (!operatorStack.empty() && !(operatorStack.top() == LeftParenthesis) && !IsUnary(currentToken))
			{
				// There is another operator (o2) on the stack.
				if (IsLeftAssociate(currentToken) && Precedence(currentToken) <= Precedence(operatorStack.top()) || 
					IsRightAssociate(currentToken) && Precedence(currentToken) < Precedence(operatorStack.top()))
				{
					// Perform the operation.
					// Push result of operation back onto the stack.
					operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
				}
				else
					break;
			}

			// Push o1 onto the stack.
			operatorStack.push(currentToken);
		}

		// If token is a left parenthesis, push to the stack.
		if (IsLeftParenthesis(token))
		{
			currentToken = LeftParenthesis;
			operatorStack.push(currentToken);
		}

		// If the token is a right parenthesis,
		// pop the operatorStack and perform operations until left parenthesis is found.
		if (IsRightParenthesis(token))
		{
			currentToken = RightParenthesis;

			while (!(operatorStack.top() == LeftParenthesis))
			{
				// Push result of operation back onto the stack.
				operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
			}

			// Now there is a left parenthesis on top of the operatorStack. Simply pop.
			operatorStack.pop();

			// If the top operator is now a function (which is possible due to parenthesis syntax), then evaluate the result of it.
			// Only do the check if the stack isn't empty.
			if (!operatorStack.empty())
			{
				if (IsFunction(operatorStack.top()))
					operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
			}
		}

		if (!operandStack.empty())
			cout << operandStack.top() << " // ";

		if (!operatorStack.empty())
			cout << operatorStack.top();

		cout << " (" << i << ")" << endl;

		lastToken = currentToken;
	}

	// There are no more tokens left to read. Perform operations until operatorStack is empty.
	while (!operatorStack.empty())
	{
		if (!operandStack.empty())
			cout << operandStack.top() << " // ";

		if (!operatorStack.empty())
			cout << operatorStack.top();

		cout << endl;

		// Push result of operation back onto the stack.
		operandStack.push(PerformOperation(operatorStack.top(), &operandStack, &operatorStack));
	}

	return operandStack.top();
}
I see several problems when porting this code to a microcontroller: -Look at all of those function calls. Would it be a better idea to make the Token-Type (which is an enum at the moment) to a struct and simply set a bunch of bool struct members when initializing them? For example members like: _isUnary, _isLeftAssociate etc. thus making most of those function calls unnecessary and saving processor cycles. Or would it actually be inefficient from a memory point of view to create a bunch of structs and deleting them again when popping them off the stack? -The stack class. I'm using two instances right now, I'll probably have to write my own. -Fundamental functions such as sin, cos, e, ln, sqrt etc. I'll probably have to write those myself too, which isn't much of a problem, but I could spend that time doing something else. -No error handling yet. I would appreciate any tips on how to optimize this code so that I wont flood my memory and don't use unnecessary processor cycles. Cheers, Chris

Share this post


Link to post
Share on other sites
Advertisement
Aside from optimizations to the algorithm itself (which I can't speculate on, not being familiar with the algorithm in question), any optimization you want to do is going to depend very, very heavily on three things:

  • Target hardware. Microcontrollers come in a truly massive array of shapes, sizes, and capabilities. Naming the actual chipset you want to target would be nice, because chances are there's someone around here who has experience with it (unless of course you're talking about something really obscure). What kind of memory solution are you wanting to set up? Does your microcontroller come with integrated RAM or would you need a secondary chipset for external storage? etc.

  • Target operating system. If there's a platform underneath your code - i.e. you are not coding against bare metal - then its quirks and behaviours will affect how you write optimal code.

  • Target compiler. If you're using a microcontroller setup, chances are there's a dedicated compiler for it. In this case, the optimization capabilities are totally up in the air - every compiler will have different strong and weak areas in the arena of automatic optimizations. That will also affect how you do manual (i.e. assembly-level) optimization.


It's certainly possible to do what you want, but we'll need quite a few more details on your plans in order to truly get your code to an optimal condition.

Share this post


Link to post
Share on other sites
If you are looking for an unsigned integer sqrt source, faster then the standard one, the following is what I use (no divisions done):

#include <string.h>

#define BITSPERLONG 32

#define TOP2BITS(x) ((x & (3L << (BITSPERLONG-2))) >> (BITSPERLONG-2))


/* usqrt:
ENTRY x: unsigned long
EXIT returns floor(sqrt(x) * pow(2, BITSPERLONG/2))

Since the square root never uses more than half the bits
of the input, we use the other half of the bits to contain
extra bits of precision after the binary point.

EXAMPLE
suppose BITSPERLONG = 32
then usqrt(144) = 786432 = 12 * 65536
usqrt(32) = 370727 = 5.66 * 65536

NOTES
(1) change BITSPERLONG to BITSPERLONG/2 if you do not want
the answer scaled. Indeed, if you want n bits of
precision after the binary point, use BITSPERLONG/2+n.
The code assumes that BITSPERLONG is even.
(2) This is really better off being written in assembly.
The line marked below is really a "arithmetic shift left"
on the double-long value with r in the upper half
and x in the lower half. This operation is typically
expressible in only one or two assembly instructions.
(3) Unrolling this loop is probably not a bad idea.

ALGORITHM
The calculations are the base-two analogue of the square
root algorithm we all learned in grammar school. Since we're
in base 2, there is only one nontrivial trial multiplier.

Notice that absolutely no multiplications or divisions are performed.
This means it'll be fast on a wide range of processors.
*/


unsigned int usqrt(unsigned long x)
{
unsigned long a = 0L; /* accumulator */
unsigned long r = 0L; /* remainder */
unsigned long e = 0L; /* trial product */

int i;
for (i = 0; i < BITSPERLONG; i++) /* NOTE 1 */
{
r = (r << 2) + TOP2BITS(x); x <<= 2; /* NOTE 2 */
a <<= 1;
e = (a << 1) + 1;
if (r >= e)
{
r -= e;
a++;
}
}
return (unsigned int) (a >> 16);
}
/*
#include <stdio.h>
#include <stdlib.h>

int main()
{
int i;
unsigned long l = 0x3fed0169L;
unsigned li = (unsigned) (l >> 16);
printf("%x\n", li);

for (i = 65135; i < 65535; ++i)
{
printf("sqrt(%u) = %u\n",
i, usqrt(i));
}
return 0;
}
*/



I have not written it, I once found it on the internet.
Maybe it's of some help to you ;-)

As to 'e'. It's just a number so you can get a good approximation.
With 'e' you can get sin and cos...not sure how you'd implement the imaginary 'i'...or you can get a Taylor serie to get a fairly good approximation on sin and cos.

Share this post


Link to post
Share on other sites
Thanks, but I wont have any problems implementing any of the fundamental functions except for maybe hyperbolic functions as I'm not too familiar with them..then again they're not THAT fundamental.

What I am currently using:

ATmega2560: http://shop.myavr.com/index.php?sp=download.sp.php&suchwort=dl89

It's got 8kB of Ram (SRAM), 256kB of Flash and I'm not sure how much EEPROM, but it says somewhere in there. Anyone with experience in programming with AVR here, I would gladly take tips.

I'm just scared that eventually the stack and heap will collide with all of those function calls, local variables and that stack class allocating memory like a mad man (well not really). If I program my own stack class, I think I'll settle for a fixed size as I'm not sure how well the malloc function of the avr-libc fills freed gaps. Right now the stack size would get too big imo, though I think it would be worse if I would implement the Token type as a struct since those function calls aren't really my biggest concern, what do you think? It may be a bit slower, but it's not like I'm using recursion or function with a lot of local variables, so these function calls shouldn't be to heavy on the stack.

External Ram would be great, I'd just slap the heap in there.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!