Darren's Weekly Nugget 01/04/2010

[tst]

Re. an implementation of a map, you may wish to look at AQ's post here.

---

F. Schubert wrote:

This is a recursive max finder that performs O(sqrt(n)) (I'm not really sure), the old way of VI Server recursion.

---

Have you considered using the Array Max & Min primitive, from the array palette?

[TCPlomp]

---

F. Schubert wrote:

This is a recursive max finder that performs O(sqrt(n)) (I'm not really sure), the old way of VI Server recursion. It is terrible slow in LV 7.1., there are performance improvements in one of the 8.x versions. Maybe somone can recode it in 2009 with native recursion (and post a snippet) and do some benchmarks (I do not have 2009, but really enjoyed the ease of recursion when using an eval-version).

to make the snippet working, you need to set reentrant execution.

Felix

---

One thing to note, you need to set Open VI option 8 to open recursive.

Ton

[Cory_K]

---

tst wrote:

---

Darren wrote:

...my response was, "Anything that you think you need recursion for, I bet I can do with a While Loop and a shift register".  That was probably an overly simplistic response on my part, but to be honest, it's pretty much always been true.

---

Luckily, you're not in school anymore, so no one is asking you to prove it 😉 . If it makes you feel better, it's a classic argument, and there are proofs showing that any recursive algorithm can also be implemented using a stack.

---

Here's my proof  

x = x

You basically have two options:

1) The programmer creates a stack and there is no need for recursion

2) The programmer uses recursion, so the operating system creates a run-time stack anyway.

Stack = Stack.

All done!

[Darin.K]

Cork K made the first point I would mention.  I would add that at least 9 times out of 10 the programmer is more intelligent than the compiler and will do a better job (if performance is key).

The second point is that there are two major reasons that recursion causes trouble.  The first is that there is no sharing of intermediate results, so there can be redundant calculations.  The Fibonacci example is one way to turn an O(n) problem into an O(n^2) one.  Write out the function calls for Fib(5) and count how many times Fib(4),Fib(3), etc. are called.  Each one is solved independently.

The second reason, as mentioned many times, is memory management, ie. the stack.  With recursion you are backing up all function evaluations and then doing them all at once.  Eventually, this takes its toll on memory, and unless the compiler is optimized for recursion, (Scheme maybe, LV no), you will eventually have problems.

Analogy.  Say you choose a low-fiber diet and now you are backing up.  For a while things are pretty nice, you are spending less time on the can.  At some point discomfort and eventually  pain sets in.  Eventually you have a wild ride.  If you choose a high-fiber diet things run nice and smooth, but you have to hit the head a few extra times.  At the end of the week you have achieved the same "ends" with two different means, but perhaps you learn the lesson that a little bit of recursion is nice, but for larger problems, perhaps a shift register is better. 

[Ray.R]

I like your analogu Darin.  And I agree with you.  To me recursion seems to add too much overhead for the processor.  Now did anyone consider multiple core processors?  Can LabVIEW select different cores for each new recursion?  Or am I already in the Twilight Zone 😮 ?

[Cory_K]

---

Ray.R wrote:
I like your analogu Darin.  And I agree with you.  To me recursion seems to add too much overhead for the processor.  Now did anyone consider multiple core processors?  Can LabVIEW select different cores for each new recursion?  Or am I already in the Twilight Zone 😮 ?

---

LabVIEW 2009 already has auto-parallelism in For loops... who knows what else it could do

But if the function is recursive, by definition it needs the previous value to continue, so they could not be processed in parallel.

Neat thought though...

[F._Schubert]

@tst: thanks for the link to the map implementation, I have overlooked it previously. Yes, I know about the primitive (I ran the code against it to test it's correctness), my intention was more to show some code, so we can discuss more in depth. Here I still would like if others will show some solutions for this 'coding challenge', and someone would benchmark them.

@Ton: I would say you are rigth with option 8, BUT: this code did run, and proves us two false. 

@Cory K, Darin.K: Functional languages have their own concepts of optimization. As the parallel architectures we use in LV, so can those languages also run in parallel, in my example in each recursion step two new threads may be generated. And this is a way you are tackling problems in these languages, hence they can (and I guess they do) support native multi-tasking. The other optimization is lazy evaluation. In short, if we have a function like 'a or b'and a evaluates to true, we do not need to calculate.

But I don't know how far LV is already using these concepts in the native recursion that was just recently introduced and wether these are on the roadmap. I also have no clue how huge the overhead still is, in 7.1 it is horrible... but in functional languages of course, this overhead is minimal (just put it onto the stack...).

Felix

[Darin.K]

A little bit of testing with the Array Max/Min shows the following:

Simple implementation (scan all elements) 2-3X slower than the primitive

Native recursion: ~ 30-40X slower than the primitive

VI server recursion: Still waiting, hopeless for more than 1000 elements.

[Henrik_Volkers]

---

Darren wrote:

---

@tst wrote:

...there are proofs showing that any recursive algorithm can also be implemented using a stack.

---

That reminds me of another great example.  Several years ago I was asked to re-write a certain NI toolkit.  One part of the toolkit had some code that parsed a third-party file format.  This code used recursive VI server calls, since there were many nested data structures in the file.  For one particularly large file, the code took over 24 hours to complete the parsing.  As part of my re-write, I trashed the old parser and wrote a new one...one which processed the file line-by-line, keeping a stack of data describing the current nesting level of the line I was on.  With this approach, the parsing time of that large file went from 24 hours to about 10 minutes.

Ever since then, I've written many parsers (some for XML, some for other formats), and I always take the line-by-line approach with a stack.

---

Darren  did you rewrite the Mass Compile?  😉

SCNR