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

Performance Improvements Using Judy Arrays

github.com

Post reply on HN
Print view View original

31–40 of 53 posts

Re: Performance Improvements Using Judy Arrays

#31

Post by Peaker »

mcintyre1994 wrote: post #29
jemfinch wrote: post #14

The article's credibility is significantly reduced by referring to Judy Trie lookups as O(log n) operations. They're actually O(log w) operations: the number of operations is bounded by the array's word size , not the size of the Judy array. A million elements in a Judy32 array will cause at most 7 node hops, not the 20 you'd expect from a binary tree.

This is the genius of tries. We had to code up the data structures for Twitter for our coursework, for some reason as if it was all in memory. I found a suffix tree (not as clever, it branches on character, so normalised there were 36, and is designed for full text searching) was a really clever way to store that data because search time for a phrase doesn't increase as your data set does. Unrealistic for something l…

Twitter's data is all in memory. That memory may not be random-access memory, though.

A pet peeve of mine is how people can do all the CS necessary to get nice data structures for their in-RAM data, but seem to forget everything they know and use very bad structures when they spill to flash or disk storage.

Re: Performance Improvements Using Judy Arrays

#32

Post by [deleted] »

jknightco wrote: post #22
revelation wrote: post #15

Earlier quoted context omitted.

That's not what I mean. I think that any half-decent implementation in C would have been better than their current Ruby solution. And instead of spending all that time to research Judy arrays and other magic bullets, they could have already identified another problem zone and fixed it. This just feels like "we have this huge and slow Ruby behemoth here, but using magic Judy arrays we made this little gear turn insane…

Execution time isn't the only cost in building software however. Building a web application in C may be "cheap" in regards to scaling performance, but it would sure as hell increase development costs a ton. I think what Github has done is exactly what you're supposed to do: build your product on a platform that allows for quick growth and easy iteration, identify the slow parts, then swap those out for faster "gears"…

[deleted]

Re: Performance Improvements Using Judy Arrays

#33

Post by aidenn0 »

jemfinch wrote: post #14

The article's credibility is significantly reduced by referring to Judy Trie lookups as O(log n) operations. They're actually O(log w) operations: the number of operations is bounded by the array's word size , not the size of the Judy array. A million elements in a Judy32 array will cause at most 7 node hops, not the 20 you'd expect from a binary tree.

Actually its O(w) and so are optimal hash-tables (since the hashing function must be O(w).

Interestingly enough you can consider hash tables and Tries to be O(log n) since in order to have N distinct keys, the maximum key length must be at least log(N).

Re: Performance Improvements Using Judy Arrays

#34

Post by twistedpair »

exabrial wrote: post #9

I would have liked to seen the Judy array implementation in pure Ruby, so we could compare apples to apples. I'm not trying to troll... but basically they solved their problem by: * Avoiding Ruby language features * Rewriting it in a different language This is why I lean towards static languages like Go, Scala, and Java.

So if you want to run a big site on Ruby, slowly migrate all the Ruby bits you use heavily to C/++? Seems to be the storyline of their blog.

Re: Performance Improvements Using Judy Arrays

#35

Post by nthitz »

anateus wrote: post #16
nthitz wrote: post #12

Sometimes Mods change the title to be the original article title. And sometimes they change it from the original article title to something else!

Yes... they change it to the original unless it's really clear the original change was super necessary. In cases when the original title tells you nothing of the content, they change it to something useful. Seems like a pretty transparent and reasonable heuristic to me.

I agree that it's reasonable. I don't feel it's applied uniformly though.

Re: Performance Improvements Using Judy Arrays

#36

Post by quandrum »

twistedpair wrote: post #34
exabrial wrote: post #9

I would have liked to seen the Judy array implementation in pure Ruby, so we could compare apples to apples. I'm not trying to troll... but basically they solved their problem by: * Avoiding Ruby language features * Rewriting it in a different language This is why I lean towards static languages like Go, Scala, and Java.

So if you want to run a big site on Ruby, slowly migrate all the Ruby bits you use heavily to C/++? Seems to be the storyline of their blog.

Well, maybe to put it more generously:

1. Build a site in ruby (insert langauge/framework the creators are most comfortable/familiar with and can iterate quickly). 2. Build a community of a certain size that causes it scaling problems. 3. Identify the hotspots and re-implement them in more performant way.

This seems entirely reasonable to me. In fact, I'm guessing this is the path that all applications that get to Github scale take. Of course, it's easy to be snarky and identify Ruby as the problem. (Building the community is the hard part!)

Re: Performance Improvements Using Judy Arrays

#37

Post by steveklabnik »

quandrum wrote: post #36
twistedpair wrote: post #34

Earlier quoted context omitted.

So if you want to run a big site on Ruby, slowly migrate all the Ruby bits you use heavily to C/++? Seems to be the storyline of their blog.

Well, maybe to put it more generously: 1. Build a site in ruby (insert langauge/framework the creators are most comfortable/familiar with and can iterate quickly). 2. Build a community of a certain size that causes it scaling problems. 3. Identify the hotspots and re-implement them in more performant way. This seems entirely reasonable to me. In fact, I'm guessing this is the path that all applications that get to Gi…

Bias alert: I have commit to Rails.

I think another bit that you've missed here is that once you have the users and are looking at scale, you've learned a lot about what you actually need. This fits well with all of the Lean Startup stuff: startups are an experiment.

In other words, before you're actually at scale, how do you know what your requirements are? Better to build things in something that lets you discover these requirements as quickly as possible, then fix an inconsistencies in what you've built, rather than try to imagine what your future requirements may be, build that, and turn out to be wrong.

To use one of the more famous examples of a pivot, if the Flickr team had spent a ton of time analyzing their anticipated needs for a game engine, that would have all been wasted when they pivoted to photo sharing.

On the smaller scale, if you asked me today why rendering GitHub's views is slow, I probably would have guessed that it's their SOA-style architecture, an overhead between components. I then could have wasted tons of time optimizing that, with little impact on what actually mattered.

But you can't take these measurements until you have a system that actually exists in the material world.

Re: Performance Improvements Using Judy Arrays

#38

Post by mcintyre1994 »

Peaker wrote: post #31
mcintyre1994 wrote: post #29

Earlier quoted context omitted.

This is the genius of tries. We had to code up the data structures for Twitter for our coursework, for some reason as if it was all in memory. I found a suffix tree (not as clever, it branches on character, so normalised there were 36, and is designed for full text searching) was a really clever way to store that data because search time for a phrase doesn't increase as your data set does. Unrealistic for something l…

Twitter's data is all in memory. That memory may not be random-access memory, though. A pet peeve of mine is how people can do all the CS necessary to get nice data structures for their in-RAM data, but seem to forget everything they know and use very bad structures when they spill to flash or disk storage.

Oops, of course. I meant we didn't have to set up/have access to persistent storage like a database.

That sounds basically exactly like our course so far. I'm only in the first year though, so I guess it's a bit early to comment on course coverage. But yep, all RAM data structures so far.

Re: Performance Improvements Using Judy Arrays

#39

Post by r00fus »

quandrum wrote: post #36
twistedpair wrote: post #34

Earlier quoted context omitted.

So if you want to run a big site on Ruby, slowly migrate all the Ruby bits you use heavily to C/++? Seems to be the storyline of their blog.

Well, maybe to put it more generously: 1. Build a site in ruby (insert langauge/framework the creators are most comfortable/familiar with and can iterate quickly). 2. Build a community of a certain size that causes it scaling problems. 3. Identify the hotspots and re-implement them in more performant way. This seems entirely reasonable to me. In fact, I'm guessing this is the path that all applications that get to Gi…

Back in my smalltalk days (mid-90s), we used to call this "going below the C level" - take sections of code that need to be optimized, and rewrite them in C as a DLL/shared binary, to be called by the smalltalk native layer.

The % of C code was less than 3%, from what I remember, and C is significantly more verbose than smalltalk, too.

I hear that happened a lot with java as well, using JNI sections for performance purposes (this was before hotspot compiler got decent).

Re: Performance Improvements Using Judy Arrays

#40

Post by snprbob86 »

Peaker wrote: post #31
mcintyre1994 wrote: post #29

Earlier quoted context omitted.

This is the genius of tries. We had to code up the data structures for Twitter for our coursework, for some reason as if it was all in memory. I found a suffix tree (not as clever, it branches on character, so normalised there were 36, and is designed for full text searching) was a really clever way to store that data because search time for a phrase doesn't increase as your data set does. Unrealistic for something l…

Twitter's data is all in memory. That memory may not be random-access memory, though. A pet peeve of mine is how people can do all the CS necessary to get nice data structures for their in-RAM data, but seem to forget everything they know and use very bad structures when they spill to flash or disk storage.

Can you recommend or link to introductory material on data structures optimized for flash and disk?
Post reply on HN