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

101–110 of 129 posts

Re: Why recursive data structures?

#101

Post by taeric »

rrobukef wrote: post #81
taeric wrote: post #72

Earlier quoted context omitted.

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.

It is always interesting to see just how valuable a "tiny bit" can be, though.

Granted, I confess most is almost always navel gazing. Increases in the "best" sorting/map algorithm have probably not lead to any noticeable improvements in modern codebases. Usually, those benefit more from being the low hanging fruit, not most computationally complex. (That is, I'm sure in these large matrix problems, there are other low hanging fruit that will yield better improvements.)

Re: Why recursive data structures?

#102

Post by themckman »

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…

> 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 implementing and playing with things, but I'd like to know about good resources for things to consider about performance on real systems. I hear about things like cache misses, memory layouts and branch mispredictions, but don't really know how to apply that knowledge or, maybe more importantly, measure the effects of optimizing for some of those things over others. I'd appreciate any advice anyone has to offer.

Re: Why recursive data structures?

#103

Post by chronial »

mypalmike wrote: post #41
stan_rogers wrote: post #26

Earlier quoted context omitted.

"Isomorphic" literally means "of the same shape".

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.

Re: Why recursive data structures?

#104

Post by OskarS »

coldtea wrote: post #87
munificent wrote: post #76

Earlier quoted context omitted.

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

It's an entirely plausible scenario. It will rarely be the case with photographs, but graphical images often feature large solid color blocks. It's large reason why the PNG file format exists.

Re: Why recursive data structures?

#105

Post by zeveb »

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?

Neither: it's probably using JavaScript to perform an AJAX request to get some data in a bespoke markup format, then using JavaScript to parse that markup format and build DOM entries, all because the developer thinks HTML is 'so 90s, dude!'

Re: Why recursive data structures?

#106

Post by braythwayt »

teddyh wrote: post #96

The algorithm to rotate images can be illustrated by running /usr/lib/xscreensaver/blitspin blitspin - rotate a bitmap in an interesting way The blitspin program repeatedly rotates a bitmap by 90 degrees by using logical operations: the bitmap is divided into quadrants, and the quad‐ rants are shifted clockwise. Then the same thing is done again with progressively smaller quadrants, except that all sub-quadrants of a…

Thanks, I have included the video and a credit to you in the essay.

Re: Why recursive data structures?

#107

Post by braythwayt »

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 .

> The thing that has the shape of a quadtree is the callgraph

Thanks, I have borrowed your succinct explanation and added it to the essay. MuchIappreciate the insight.

Re: Why recursive data structures?

#108

Post by Const-me »

themckman wrote: post #102
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…

> 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 locality while reading outweigh the losses from relocating those elements while inserting).

Modern hardware is extremely complex. No amount of knowledge will help you to 100% predict the performance effects of your changes. Two advices.

(1) Learn to profile your code. Both externally, using a sampling profiler that will tell you where’re you spending the CPU time, and internally using e.g. std::chrono::high_resolution_clock that will tell you the performance effect of your changes.

(2) Don’t forget about rollback feature of your version control, and don’t hesitate using that as necessary. I routinely discover some of my changes I viewed as performance optimizations actually decreased performance. The reasons include branch misprediction, compiler optimization issues, cores competition for L3 cache, RAM bandwidth, thermal issues…

Re: Why recursive data structures?

#109

Post by GFK_of_xmaspast »

taeric wrote: post #100
GFK_of_xmaspast wrote: post #99

Earlier quoted context omitted.

The mention of "around 10% or less" is based on a 2005 paper, and even in the past ten years there's been a lot of change in computer architecture (the machines used in the paper were mostly ultrasparcs, and they write "Note that for the (pentium 3 system), we could find no problem size for which Strassen’s is faster than ATLAS’s"). See also : https://www.quora.com/What-algorithm-does-BLAS-use-for-matri... https://gi…

That is an interesting note. I remember reading that the lower bound on multiplications was lower due to swapping a lot of them for additions. Knuth indicated that this did not matter in practice, since few people are multiplying large matrices. My interest here is really just if that is still a good assumption. With the multiplications that happen in "deep" fields, I'm curious if there are now reasons to look to the…

We might be talking at cross-purposes, my angle is that of dense linear algebra, single or double precision, on NUMA architectures with vector operations, and all respect to Knuth but it requires a different model for the machine.

If that's changed, like for example if you're computing over a different ring where arithmetic ops are expense as compared to cache misses and there's no stability issues, then yes the issue is back open and Strassen is put back on the table.

Re: Why recursive data structures?

#110

Post by Patient0 »

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

Earlier quoted context omitted.

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

Well, hierarchical representation of those images is indeed a good idea for some data. Saves both RAM space and bandwidth, and CPU time. Just not the quad-tree way described in the article. There are ways to implement hierarchical structures that work well on modern hardware. One is hashmaps keeping dense 2 bits per pixel blocks (again, 16-64 bytes per block) with the values saying filled/empty/mixed. Another one is…

How would you improve on the quad-tree representation used to implement hashlife? http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...
Post reply on HN