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

121–129 of 129 posts

Re: Why recursive data structures?

#121

Post by inimino »

coldtea wrote: post #86
inimino wrote: post #63

Earlier quoted context omitted.

>> 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.

By that argument, any blog post that does not contain a comprehensive software development education can be criticized.

You should ask whether these techniques are useful in writing correct code and if they save developer effort, rather than picking apart irrelevant aspects of the toy example.

I don't think modern graphics code represents individual pixels as strings either, would you dismiss the post for that reason?

Re: Why recursive data structures?

#122

Post by fanf2 »

Const-me wrote: post #118
braythwayt wrote: post #113

Earlier quoted context omitted.

I believe most modern implementations, including hybrid implementations of HashLife, take advantage of register and cache sizes. HashLife as I might implement it in JavaScript, is really a very naïve approach. I think Bill Gosper even had versions in the 1970s that did things with registers and assembly, not just doing everything in lists. But the big issue with HashLife is not whether you can write a faster implemen…

Looking at golly-2.8-src. At the first sight, it does not use SIMD. Only uses 32-bit registers in 32-bit builds, 64-bit registers in 64-bit builds. All x86 CPUs manufactured after 2003 have at least 16 128-bit SIMD registers. Using them for calculations is the only way to get anywhere near advertised CPU performance. For languages other than C and C++, like JavaScript, where there’s no SIMD instructions, calculations…

For JavaScript you might do quite well with a 32-way bit-slice implementation, like http://fanf.livejournal.com/93032.html That is, if you can't do it on the GPU with WebGL :-)

Re: Why recursive data structures?

#123

Post by fanf2 »

Const-me wrote: post #108
themckman wrote: post #102

Earlier quoted context omitted.

> Apparently, every computer science problem has easy to understand solution that’s easy to implement but awfully slow in practice. I have been doing some data structures/algorithms review as I haven't really used much of that knowledge from my CS degree and, frankly, wasn't that great of a student when I was learning it. I've obviously focused mostly on understanding theoretical performance (Big-O) as I've been impl…

That Big-O thing is mostly theoretical. Most useful application is job interviews. It might stop you from doing some things, like bubble-sorting 1GB datasets, or inserting many elements to the start of a large array. However, in other cases it’s just fine to bubble-sort (for very small collections), or insert many elements to the start of the array (when you’re reading much more often so the profit from memory locali…

For a dose of real-world big-O I recommend following http://accidentallyquadratic.tumblr.com

Re: Why recursive data structures?

#124

Post by sangnoir »

hinkley wrote: post #75
ivraatiems wrote: post #67

Earlier quoted context omitted.

A slow solution isn't wrong. Just inefficient.

We're talking about several orders of magnitude here. Is a web page that loads in fifty seconds 'correct' or is it wrong? Is a video format that can only decode 2 frames per second correct, or wrong? Often, timeliness is an unstated part of the requirements, in which case an academically pleasing solution that isn't practical doesn't fulfill the requirements.

> Is a web page that loads in fifty seconds 'correct' or is it wrong?

Of course it is correct - this is how the internet was/is with a 14k or 56k dialup modem, I don't blame you for not remembering/not experiencing it. I remember watching JPEGs render progressively from a blurry mess one at a time, or sometimes not at all. It took way more than 50 seconds to load and render all elements on a typical website.

Re: Why recursive data structures?

#125

Post by braythwayt »

Const-me wrote: post #118
braythwayt wrote: post #113

Earlier quoted context omitted.

I believe most modern implementations, including hybrid implementations of HashLife, take advantage of register and cache sizes. HashLife as I might implement it in JavaScript, is really a very naïve approach. I think Bill Gosper even had versions in the 1970s that did things with registers and assembly, not just doing everything in lists. But the big issue with HashLife is not whether you can write a faster implemen…

Looking at golly-2.8-src. At the first sight, it does not use SIMD. Only uses 32-bit registers in 32-bit builds, 64-bit registers in 64-bit builds. All x86 CPUs manufactured after 2003 have at least 16 128-bit SIMD registers. Using them for calculations is the only way to get anywhere near advertised CPU performance. For languages other than C and C++, like JavaScript, where there’s no SIMD instructions, calculations…

For HashLife, I think the chief problems are around an efficient cache, and especially efficient canonicalization. The algorithm is so fast for universes that suit its domain that I think most other considerations drop by the wayside.

However, besides the fact that not all problems have enough redundancy in time+space to suit it, it also suffers from the fact that it is most efficient when computing massive jumps in generations. So it’s as not as performant for creating animations as it is for doing things like finding the maximum size of a pattern, calculating its growth rate, and so forth.

Re: Why recursive data structures?

#126

Post by Const-me »

fanf2 wrote: post #123
Const-me wrote: post #108

Earlier quoted context omitted.

That Big-O thing is mostly theoretical. Most useful application is job interviews. It might stop you from doing some things, like bubble-sorting 1GB datasets, or inserting many elements to the start of a large array. However, in other cases it’s just fine to bubble-sort (for very small collections), or insert many elements to the start of the array (when you’re reading much more often so the profit from memory locali…

For a dose of real-world big-O I recommend following http://accidentallyquadratic.tumblr.com

I don’t think engineers working at Ericsson and Apple (the companies listed in the copyright section of that source file) forgot about big-O. What I think happened, when they wrote that, their assumption was people won’t be using those to pass 16MB blobs. And for small messages, O(n^2) works just fine.

I can understand those people. HTTP is better than Web Sockets for large chunks of data. With HTTP, servers and proxies may cache, clients may resume downloads, clients may check for changes with if-modified-since header, and so on.

The problem here isn’t with big-O, it’s with changing world.

If in the future someone will send gigabytes in that event, the current version will break despite O(n), because RAM is finite. Relatively easy to fix, you just need to save data to a hard drive instead or RAM.

Does it mean it’s a good idea to do so now? Don’t think so, it would be over-engineering and premature optimization, and the current version is currently fine. Just like the original O(n^2) code was fine for small messages.

Re: Why recursive data structures?

#127

Post by iamaelephant »

Wait, the way he defines the quad tree color property requires that you manually input the color for each region. If you wanted this to be part of a general purpose algorithm in real software then you'd need another algorithm that determines the color of each region - a very expensive operation if you wanted the maximum benefit.

Re: Why recursive data structures?

#128

Post by pwm »

lacampbell wrote: post #16
ianamartin wrote: post #14

I love the word "isomorphic". It's by far the most efficient word in the English language. When someone else uses it in conversation, it's absolutely guaranteed that the person is a pretentious asshole. When you use it in a conversation, the same is also true. It's only ever acceptable in written contexts or if you happen to be Douglas Hofstadter.

> When someone else uses it in conversation, it's absolutely guaranteed that the person is a pretentious asshole. I don't get your angle here. You realise an isomorphism is actually a well-defined mathematical concept, right? Are you advocating we use another, plainer word for an isomorphism, or do just naturally get angry when you hear words you don't understand?

> You realise an isomorphism is actually a well-defined mathematical concept, right?

I think a prime example of how words loose their precise mathematical meaning is the word "function". It has a precise definition in maths but we programmers use it often with a different meaning. We used to have the terms "subroutine" and "procedure" for what we use "function" for nowadays. We even came up with the term "pure function" to refer to the original mathematical meaning of "function".

Re: Why recursive data structures?

#129

Post by mypalmike »

chronial wrote: post #103
mypalmike wrote: post #41

Earlier quoted context omitted.

Even with a non-mathematical definition such as yours, I don't see the isomorphism. Recursive code that acts on a quadtree does not itself take the shape of a quadtree. Not the text, not the AST, not the machine code. The code is treelike, but that's because all code is treelike(1). As a counterexample, consider code that acts on arbitrary graphs. DFS on an arbitrary graph doesn't itself take the form of an arbitrary…

The thing that has the shape of a quadtree is the callgraph. That means there is one call for every instance of the data class, which makes it easy to reason about the code. See also my answer to the parent: https://news.ycombinator.com/item?id=13306762 .

Reading through some ancient conversations...

OK so the callgraph is isomorphic in some sense when using recursion. If this was the intent of the author, it was not clear.

I would still argue that call-graph isomorphism to the data structures they work is of little relevance to software practitioners.

1. Multithreaded algorithms acting on trees do not necessarily have callgraphs that are isomorphic to the trees.

2. As I mentioned elsewhere, arbitrary graph data structures, or even the more constrained subset of DAGS, are not isomorphic to call graphs of the algorithms that work on them. Recursive algorithms have the same exact applicability to these structures as they do quadtrees.

3. Also as I mentioned elsewhere, recursive algorithms can be implemented with loops and an explicit stack without any function calls at all. This is at times the best way to implement algorithms on trees (particularly where trees are deep and the platform has a small stack - yes I've had to do rewrite recursive code because it overflowed a small, non-configurable stack).

Post reply on HN