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

111–120 of 129 posts

Re: Why recursive data structures?

#111

Post by Const-me »

Patient0 wrote: post #110
Const-me wrote: post #94

Earlier quoted context omitted.

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

I wouldn’t.

I am not convinced hashlife is still the best of them. The invention is from early 80-s. Many old heuristics about caching versus calculation is no longer true today. Here’s my article on the related topic, lookup tables: https://github.com/Const-me/LookupTables

If I wanted to implement efficient life simulator, I’d probably used the fact that with AVX2, it’s possible to count those neighbors for 8x8 block of pixels in a single __m256i register (with 8 neighbors max, 4 bits / value is more than enough). Might be faster than L3 cache access, and will definitely be much faster than main memory access.

That’s why I’d put those pixels in 8x8 blocks, single uint64_t value per block.

Putting those blocks in a hash table takes care about the infinite field. std::unordered_map will work, but if you care about performance prefer CAtlMap from Microsoft, dense_hash_map from Google, or something similar.

Re: Why recursive data structures?

#112

Post by taeric »

GFK_of_xmaspast wrote: post #109
taeric wrote: post #100

Earlier quoted context omitted.

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 issu…

Knuth seems to be in agreement with you, from my understanding. My comments are only of a general interest and curiosity, not of knowledge. (If that makes sense.)

That is, I certainly was not trying to second guess what you are saying. Just noting my curiosity on whether or not this has, or will, change. Knuth's view that I'm quoting is from Vol 2, which is pretty old at this point. I'd be a little surprised if it was outdated. But not shocked.

Re: Why recursive data structures?

#113

Post by braythwayt »

Const-me wrote: post #111
Patient0 wrote: post #110

Earlier quoted context omitted.

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

I wouldn’t. I am not convinced hashlife is still the best of them. The invention is from early 80-s. Many old heuristics about caching versus calculation is no longer true today. Here’s my article on the related topic, lookup tables: https://github.com/Const-me/LookupTables If I wanted to implement efficient life simulator, I’d probably used the fact that with AVX2, it’s possible to count those neighbors for 8x8 bloc…

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 implementation, it's whether the particular pattern(s) you are exploring are amenable to HashLife. It wins for highly repetitive patterns, but is much slower for patterns with a very large amount of entropy in time and space, like methuselahs.

HashLife can be fabulous for exploring purpose-built machines that cycle though regular states.

Re: Why recursive data structures?

#114

Post by braythwayt »

stephenboyd wrote: post #55

As a web developer, I appreciate this rare use of JavaScript in a CS lesson.

JavaScript is the language most likely to be familiar to the audience I'm trying to reach. But at a certain point, it gets in the way of explaining an idea rather than making it easier.

I think this essay stays on the right side of that trade-off.

Re: Why recursive data structures?

#115

Post by braythwayt »

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…

Although I'm satisfied with the choice I made for what to put in my essay, I want to thank you for pointing out the gaps between my essay and the real world, and for doing so in a forceful way without crossing into being querulous.

This kind of discourse is, IMO, an example of Hacker News at its finest.

Re: Why recursive data structures?

#116

Post by braythwayt »

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…

Although I'm satisfied with the choice I made for what to put in my essay, I want to thank you for pointing out the gaps between my essay and the real world, and for doing so in a forceful way without crossing into being querulous.

This kind of discourse is, IMO, an example of Hacker News at its finest.

Re: Why recursive data structures?

#117

Post by braythwayt »

johnfn wrote: post #85

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.

Author here. Nevertheless, there's learning gold in those comments. Take the gold, leave the mud.

Re: Why recursive data structures?

#118

Post by Const-me »

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

Earlier quoted context omitted.

I wouldn’t. I am not convinced hashlife is still the best of them. The invention is from early 80-s. Many old heuristics about caching versus calculation is no longer true today. Here’s my article on the related topic, lookup tables: https://github.com/Const-me/LookupTables If I wanted to implement efficient life simulator, I’d probably used the fact that with AVX2, it’s possible to count those neighbors for 8x8 bloc…

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 are generally slower, but the hash tables are provided by the platform and hence implemented in highly-optimized C code, HashLife should be perfectly fine.

Re: Why recursive data structures?

#119

Post by cousin_it »

phkahler wrote: post #98
SomeStupidPoint wrote: post #60

Earlier quoted context omitted.

Could you go on a bit more (or post a link to somewhere you do)?

I've been hoping to put the code online for a long time, but I'm suffering from "it's not cleaned up enough" syndrome. But I'll talk a little here. I'd been after real time ray tracing since the 1990's so I had a goal of putting both static environments and dynamic objects/players in the same acceleration structure. A lot of the old BSP-tree stuff or other BVH are used only for static geometry and I didn't like that.…

Nice puzzle! I think you can allow both kinds of deletions while still using four pointers per link node:

* prev1 XOR next1

* prev2 XOR next2

* prev1 XOR prev2

* data1 XOR data2

Because while traversing you always know one of {prev1, prev2} and one of {data1, data2}. Right?

Re: Why recursive data structures?

#120

Post by jaredtobin »

dukerutledge wrote: post #4

Reginald is definitely hinting at hylomorphisms here. I'd be curious to see if stream fusion could be achieved in JS for a hylomorphism.

It's exactly a hylomorphism. Here's a possibly more familiar-looking Haskell form:

    {-# LANGUAGE DeriveFunctor #-}
    {-# LANGUAGE LambdaCase #-}

    import Data.Functor.Foldable
    import Data.List.Split

    data QuadTreeF a r =
        NodeF r r r r
      | LeafF a
      | EmptyF
      deriving Functor

    builder :: [a] -> QuadTreeF a [a]
    builder = \case
      []  -> EmptyF
      [x] -> LeafF x
      xs  -> NodeF a b c d where
        [a, b, c, d] = chunksOf (length xs `div` 4) xs

    consumer :: QuadTreeF a [a] -> [a]
    consumer = \case
      EmptyF            -> []
      LeafF a           -> [a]
      NodeF ul ur lr ll -> concat [ll, ul, ur, lr]

    rotate :: [a] -> [a]
    rotate = hylo consumer builder
Post reply on HN