41–50 of 53 posts
I wouldn't have used the prefix approach, instead storing a token once in the judy array, and using the data stored to indicate which languages match the token.
Earlier quoted context omitted.
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?
One useful data structure is the B+ tree http://en.wikipedia.org/wiki/B%2B_tree
The graphs never show a 30K token mark, which is what the heap-allocation counter showed for their [programming language] classifier.
It's not clear to me that much RSS was saved. Maybe 20Mb? So, the next question is how many classifiers are running, where such a "hit" actually matters. Again, there is no 30K mark on the runtime graphs, but let's assume the generation to the graphs' left are linear. It looks like we're saving a half-second and removing most of the jitter, but it's not made clear how the removal of GC chunking has any effect on processing outside of the classifier. I just can't imagine how a couple of these classifiers can't keep up with the push rate of files to Github -- the classification improvements are neither low-hanging or part of the BigO in Github's stack. The process seems very able to run asynchronous at push time and un-deferred, if unrun, on page view. Unless they're seeing more than 1 million pageviews/sec (per classifier; just run more? one 20Mb service per httpd server?), because I can't really imagine hitting more than 10x their tokens (300K tokens), which is still only ~50Mb; the RSS graph, again, has a weird scale to suggest they might grow their tokens by 67x.
Earlier quoted context omitted.
Can you recommend or link to introductory material on data structures optimized for flash and disk?
You could start by looking at databases. One useful data structure is the B+ tree http://en.wikipedia.org/wiki/B%2B_tree
http://en.wikipedia.org/wiki/Log-structured_merge-tree
There're a bunch of fascinating performance tradeoffs between B+ trees and LSM trees, which come out when you're choosing between something like MySQL InnoDB or PostGres (B+ tree) vs. LevelDB or Apache Cassandra (LSM trees). LSM trees tend to be faster for inserts and for write-heavy applications, and they offer very fast reads and writes for frequently-accessed data. They also depend upon the bandwidth of the disk rather than the seek time, and bandwidth has of late been increasing significantly faster than seek times. OTOH, they offer very variable latency, as an insert might trigger a major compaction, while B+ trees have a bounded latency limit. A lot of the distributed systems work at Google (a big user of LSM trees via BigTable) comes from the need to work around the poor 99th percentile latencies of LSM trees.
Earlier quoted context omitted.
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.
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.
A web app involved in a site as complex as Github's should really contain only the parts required to service web pages. A service like language classification is clearly better designed as a standalone service.
Aside from working around GC overhead, compositing big app from many smaller apps have many advantages. You force yourself to encapsulate complexity with strictly focused, network-friendly APIs (we use REST ourselves), which changes the way you have to think about programs. Hiding the implementation behind an API also allows you to swap out the implementation without the client ever knowing. Since the client and server are separated, you have fine-grained control over how much resources you are willing to spend on which components. And so on.
Having done monolithic Rails apps for many years, it's a model I am not going to back. Today, our web apps contain only UI logic. No database, no models, no data logic, just UI all the way. Everything else is handled by specialized components.
For starters, the blog post was informative and should get some creative juices flowing for applications in others' stacks -- piqued my interests in hacking core utilities. However... The graphs never show a 30K token mark, which is what the heap-allocation counter showed for their [programming language] classifier. It's not clear to me that much RSS was saved. Maybe 20Mb? So, the next question is how many classifier…
Earlier quoted context omitted.
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?
2. unconvinced that they can't do better w/ the right hash table (which will be thousands of lines fewer of code). but since they're using a library, i'll give them a pass. not even a benchmark vs. a quick hash table version makes all the claims about "judy arrays are better for our purpose" suspect.