Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why recursive data structures?

raganwald.com

Post reply on HN
Print view View original

81–90 of 129 posts

Re: Why recursive data structures?

#81

Post by rrobukef »

taeric wrote: post #72
GFK_of_xmaspast wrote: post #69

Earlier quoted context omitted.

Recursive matrix multiplication is in general a bad idea (Strassen, for example, loses a little bit of stability and is not cache-friendly)

To be clear, I can see why coding it purely recursively would be a bad idea. Same for using linked structures, if that was the concern with the quad tree. However, it seems that you could use the general recursive definition to find some optimizations that one could do. For example, define a recursive structure to break down a problem until it is small enough that a more traditional method works. (So, don't drop down…

Very large matrices is >50kx50k (maybe even bigger). Strassen is then just a tiny bit better when implementing both cache and allocation aware.(Tested in Fortran)

At least it's at a non practical size.

Re: Why recursive data structures?

#82

Post by tallanvor »

eridius wrote: post #2

The footnotes say that all the functions can be adjusted to deal with non–power-of-2 squares, but it's not obvious how this is done when working with region quadtrees.

Yes, that made me lose a lot of confidence in the article. This shouldn't have been a footnote. It should have been stated in the beginning that the author was only considering powers of two, and the footnote should have been a reference to ways to deal with other sizes - my very first question, before I got to the footnotes, was "How would I deal with a 3x3 square?"

Re: Why recursive data structures?

#83

Post by lomnakkus »

tedunangst wrote: post #23
lacampbell wrote: post #19

Earlier quoted context omitted.

> But if we’re going to be serious about it, technical jargon is really only appropriate when the speaker is 100% sure the audience 100% understands it. I disagree. Half the reason I come here is to be exposed to new ideas or concepts. This isn't a lecture, I'll gladly take time to learn about a new concept if it seems relevant.

Since we're on the subject of recursion, there is a problem when somebody uses a term that they only understand 90%. Somebody else reads that and understands 90%, and then they use, and then another person reads it... And then we arrive in the current situation where people use terms like "rainbow table" or "HFT" to describe who knows what.

Isn't that just the general nature of human communication, though?

I mean, yeah, maybe one could argue about math, but even math (proofs, especially[1]) can get a bit fuzzy.

[1] Which one could argue are a prerequisite for true understanding of a mathematical concept.

Re: Why recursive data structures?

#85

Post by johnfn »

I really enjoyed this article because it introduced me to a new data structure and some very elegant and (subjectively) beautiful algorithms. I came onto HN expecting some insightful commentary and instead got 80 comments griping about how it wasn't 100% optimized.

Sigh.

Re: Why recursive data structures?

#86

Post by coldtea »

inimino wrote: post #63
Const-me wrote: post #49

Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. This is one of them. Rotating images that way isn’t CPU bound problem. It’s RAM bandwidth and RAM latency bound problem. The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If they…

>> we’d provide much snappier behaviour using coloured quadtrees > That statement was true 30 years ago, no longer a case. The colored quadtrees are an optimization over the plain quadtrees earlier in the article, reducing the number of comparisons for some images. That will be more efficient 300 years from now just as much as it was 30 years ago. In context it is perfectly obvious that "much snappier" does not refer…

>It's a toy implementation used as an example, if you get hung up on the example, you miss the whole point.

When to use such techniques, and whether they make sense in the real world, performance wise, should have been part of the "whole point" all along.

Re: Why recursive data structures?

#87

Post by coldtea »

munificent wrote: post #76
Const-me wrote: post #49

Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. This is one of them. Rotating images that way isn’t CPU bound problem. It’s RAM bandwidth and RAM latency bound problem. The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If they…

> The optimal data structure for that is not recursive, it’s 2D array of small square blocks of pixels. If pixels are bits, I’d bet on either 8x8 or 16x16 blocks. If the image is very large and contains large contiguous regions of solid colors, then a quadtree that doesn't subdivide homogeneous regions can be a much faster approach than a flat pile-o-pixels. Either way, this article isn't about rotating images.

>If the image is very large and contains large contiguous regions of solid colors

In other words, if the image is not very image-y? (but more vector-y).

Re: Why recursive data structures?

#88

Post by coldtea »

ivraatiems wrote: post #67
hinkley wrote: post #56

Earlier quoted context omitted.

For every complex problem there is an answer that is clear, simple, and wrong.

A slow solution isn't wrong. Just inefficient.

Depends on the business constraints. Wrong is not just "returns invalid results".

There's also the notion of wrong or right solution for a particular problem (which the phrase above already assumes). E.g. for a game where things have to run in 60hz, a slow algorithm would be the wrong solution to use.

The reverse is also true: a solution can return wrong results in the absolute sense (e.g. false positives) and still be correct for our business case. This is the case with things like Bloom filters for example.

Re: Why recursive data structures?

#89

Post by lmm »

devty wrote: post #64
iamleppert wrote: post #58

Recursion is often times less efficient than a well designed and concrete imperative solution, even if the imperative solution uses more memory. This is because most languages, the stack is not free. There's a lot of meta data and house keeping that goes on when you invoke a function to support things like stack traces and introspection. The provided example (at least to me) is also convoluted and fails to illustrate…

Are you aware of a programming language/compiler that optimizes on recursively written code? I'm finding it difficult to imagine a PL where stack _isn't_ free except tail-recursive code.

Haskell (sometimes) does this kind of thing much more efficiently - it doesn't specify or always provide a stack, it models the program as a graph to be evaluated by reduction. And any language where you can implement continuations allows you to write this kind of thing efficiently (e.g. https://github.com/Atry/memcontinuationed ).

(Ultimately you can do "userspace continuations" in any programming language by explicitly transforming your code into CPS, using an explicit FSM if the language doesn't support tail-calls as such, the only price being developer sanity)

I do think there's a real gap in many languages between the natural way to express graph/tree transformations (recursively) and a cache-friendly/mechanical-sympathy-style runtime - see e.g. https://medium.com/@gkossakowski/kentucky-mule-limits-of-sca... . And really this gap shouldn't be there - the language implementation should be able to transform and fuse this kind of tree-walking operation into an efficient implementation - but at the same time it's hard to see how you'd ever make the language spec permit this without resorting to a full-Haskell "everything is lazy everywhere and the language implementation is allowed to evaluate whatever it likes however many times it likes (including 0) in whatever order".

Re: Why recursive data structures?

#90

Post by junke »

andreareina wrote: post #66
devty wrote: post #64

Earlier quoted context omitted.

Are you aware of a programming language/compiler that optimizes on recursively written code? I'm finding it difficult to imagine a PL where stack _isn't_ free except tail-recursive code.

My understanding is that it's the opposite -- function calls expend a cost to save (and later restore) the registers and push the locals onto the stack. Tail recursive functions on the other hand can be implemented as a jump to the top of the function, right after all the stack bookkeeping, and so saves on that expense.

Tail-merging doesn't only apply to recursive functions. As soon as you don't need to store intermediate result, you can jump to another function without allocating a frame.
Post reply on HN