CODEWITHSUNDEEP
algorithm
Dryadwoods
Dryadwoods

Reputation: 2929

Performance algorithm - Ordering - Tree (data structure) only solution?

I have a problem at hand, at first sight it looks easy and it is, however I am looking for some other solution (maybe more easy one):

Expressions:

V0
V1
V2
V3
V4
SumA = V1 + V2
SumB = SumA + V3
SumC = SumB + SumA
SumD = SumC + V0

As we can see here, the "base" variables are V0, V1, V2, V3 and V4 (the value of each one of them is returned from DB queries)

The user ask the software to return the result of V1 and SumC.

Solution that I know:

Find all necessary variables: V1, SumC, SumB, SumA, V3, V2

For performance I just want to process the math of each variable JUST ONE TIME.

This means that I need to order the expressions from "base expressions" to "top variables".

At this point I am only seeing a solution of the type "Tree (data structure)" > Get V1, V2 and V3 Then get SumA, after get SumB and only at last get SumC.

Is there any other way to solve this problem?

The final objective in this algorithm is to use with more complex variables and several "middle variables". So, performance is critical, I can't make the same math operation more than 1 time.

Upvotes: 3

Views: 146

Answers (4)

Tomas Pruzina
Tomas Pruzina

Reputation: 8877

Only way to speed this up is to use serialisation on level you can't get programatically unless you use your own hardware. Example: enter image description here

Please ignore note on top right, this is stolen from my script :)

Case A: 100 * 4 cycles

Case B: First result takes 3 cycles, each next takes only 1 (serialisation, Ford factory like). - 102 cycles

102 vs 400 - roughly 4* the speed.

Modern CPUs can do this to some extent automatically, but it's pretty hard to measure it. I've heard that ICC (intel C compiler) does optimize it's assembly to exploit this as much as possible, maybe that's partially why they beat everything else on intel CPU's :)

Upvotes: 0

Aaron Digulla
Aaron Digulla

Reputation: 328556

First of all, you need to build a tree with all expressions. Trees are the most simple data structure for this case.

Now let's assume you have these formulas:

SumA = v1 + v2
SumB = v1 + v2 + v3
SumC = ...

and the user asks for SumB (so you know how to calculate SumC but to make the user happy, you don't have to).

In Memory, this looks like so:

SumA = Add( v1, v2 )
SumB = Add( Add( v1, v2 ), v3 ) )

The next step is to define compare operators which tell whether two sub-trees are the same. Running those, you will notice that Add( v1, v2 ) appears twice, so you can optimize:

SumA = Add( v1, v2 )
SumB = Add( SumA, v3 )

This means you can achieve the result by the minimum of calculations. The next step is to add caching to your operators: When someone asks their value, they should cache it so the next getValue() call can return the last result.

That means evaluating either SumA or SumB will fill the cache for SumA. Since you never ask for the value of SumC, it's never calculated and therefore costs nothing.

Upvotes: 1

amit
amit

Reputation: 178411

I am not sure I completely understand - but I think you are referring to common subexpression elimination, [or something similar to it] which is a very common compiler optimization.

One common way of doing this optimization is using a graph [which is actually a DAG] of the expressions in the program, and adding iteratively new expressions. The "sources" in your DAG are all initial variables [V0,V1,V2,V3,V4 in your example]. You can "know" which expression is redundant if you already calculated it - and avoid recalculating it.

These lecture notes seems to be a decent more detailed explanation [though I admit I did not read it all]

Upvotes: 2

Nikhil
Nikhil

Reputation: 3152

Maybe you could simplify it into this and eliminate the middle step:

SumA = (V1 + V2)*2
SumC = V3 + SumA

Upvotes: 0

Related Questions