Isn't Judy Array patented? What's the legal status using it?
Performance Improvements Using Judy Arrays
21–30 of 53 posts
Re: Performance Improvements Using Judy Arrays
#22Earlier quoted context omitted.
Slow platforms are exactly where you need to talk algorithmic complexity. Switching to a faster environment would only reduce a routine's execution time by a constant multiplier—switching algorithms has the potential to do much more.
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" as you said.
Edit: I find it rather humorous that you find algorithmic research to be a magic bullet, but believe switching platforms to be a viable solution when faced with a bottleneck. I believe you have that backwards :)
Re: Performance Improvements Using Judy Arrays
#23Somebody finally found a use for them!
Re: Performance Improvements Using Judy Arrays
#24Isn't Judy Array patented? What's the legal status using it?
If patent does apply (and there's been no statement or claims about which ones do definitely apply), then people assume it's US6735595: Data structure and storage and retrieval method supporting ordinality based searching and data retrieval.
The software from HP is under the LGPLv2.1 which says "Finally, software patents pose a constant threat to the existence of any free program. We wish to make sure that a company cannot effectively restrict the users of a free program by obtaining a restrictive license from a patent holder. Therefore, we insist that any patent license obtained for a version of the library must be consistent with the full freedom of use specified in this license."
That can imply that there are no additional patent protections should you use the LGPL'ed version of Judy or its derivatives. YMMV. Consult your nearest patent attorney for details.
The patent expires in 7.5 years.
Re: Performance Improvements Using Judy Arrays
#25I 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.
Have a look at Crystal as well. https://github.com/manastech/crystal
holy wow!
Re: Performance Improvements Using Judy Arrays
#26Earlier 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"…
I don't think parent is suggesting the whole website be written in C. I think parent sees the CS focus as a sideshow, and that a C version of the "escaper," even if not designed ideally, would still smoke the Ruby version that was acting as a bottleneck.
Re: Performance Improvements Using Judy Arrays
#27I 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.
Their problem was mostly related to the choice of data structure and the object allocation and subsequent garbage collection, not dynamic typing. I don't see how any of those languages would have helped, except by having a better garbage collector, in the case of Java and Scala.
Re: Performance Improvements Using Judy Arrays
#28The 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.
7 node hops? It should be at most 4. Judy32 has a maximum branching factor of 256, and log base 256 of 2^32 is 4.
Re: Performance Improvements Using Judy Arrays
#29The 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 like Twitter, but a really useful trick that this article definitely misses.
Re: Performance Improvements Using Judy Arrays
#30Earlier quoted context omitted.
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"…
I don't think parent is suggesting the whole website be written in C. I think parent sees the CS focus as a sideshow, and that a C version of the "escaper," even if not designed ideally, would still smoke the Ruby version that was acting as a bottleneck.
"...parent sees the CS focus as a sideshow..."
My point is that the CS is never a sideshow. Improvements gained from changes in algorithmic complexity vastly outpace improvements gained from switching languages/platforms.
Worry about your algorithm first and your platform second.