leif

20 ms·

151.
by leif 14y ago
That's a bold and narrow claim to make. How do you know with what I'm concerned? It sounds like you consider the organization of your data a loftier thing to worry about than memory management. They don't sound that different to my ears,
152.
by leif 14y ago
Oh most definitely. Can't believe I forgot it.
153.
by leif 14y ago
It's that you haven't used C. Learning C teaches you something about programming that other languages can't. It teaches you ways of thinking about problems that are useful even when you aren't using C. This is true of most languages, and
154.
by leif 14y ago
IMHO you're not an experienced programmer, but there will always be someone below you on the stack, so I should shut my loud mouth before someone puts my words in it. To your request, this is not a good place to start. By the table of conte
155.
by leif 14y ago
Here are some: http://opendatastructures.org/ http://www.cgal.org/ http://pigale.sourceforge.net/ http://www.algorithmic-solutions.com/leda/index.htm Oh yeah, and this: http://graphics.stanford.edu/~seander/bithacks.html It's not
156.
by leif 14y ago
If you're doing queries across a 5MB database frequently on a phone, you should think carefully about your indexes because you're responsible for battery life.
157.
by leif 14y ago
You're right, I skimmed and that's my fault. However, it's worth noting that these sorts of attacks can give privilege escalation, not just DoS.
158.
by leif 14y ago
Not a new attack. There is a decent history of an arms race in TOCTTOU races in access/open that leads to this type of algorithmic complexity attack against bad hashing. Maybe btrfs does worse things if you do this but it's not alone. See
159.
by leif 14y ago
"Use large block writes and small block reads" Yep. Write amplification is a big deal on SSDs and gets worse due to their internal garbage collection, if you give them a high-entropy write pattern. This is not a problem though, with TokuD
160.
by leif 14y ago
"You've never visited a google restroom before?" It may surprise you to learn that most people haven't.
161.
by leif 14y ago
You edited before I submitted :)
162.
by leif 14y ago
The problem is that authenticating the customer is harder than authenticating the bank. If I call my bank, I can pretty well trust (within reason) that I've reached my bank. Once that happens they can authenticate me by asking for my privat
163.
by leif 14y ago
There's a link at the top of the article.
164.
by leif 14y ago
The cache oblivious streaming b-tree paper is the one to read. We would like to write more papers about some of the things we have discovered while implementing it, but haven't really found the time.
165.
by leif 14y ago
We don't do anything super special here. Most databases have some notion of "node" (or in mongo, "bucket", to distinguish from a machine as a node in a cluster), and keep track of which nodes in memory are clean or dirty. We log all operati
166.
by leif 14y ago
Hi, I'm one of the authors (I'm an engineer, not an author of the original papers, though I can discuss those too)! What would you like to know? First, the structure you described is called a cache oblivious lookahead array (COLA), and is n
167.
by leif 14y ago
And doesn't moving the decimal point chop off between 6 and 7 bits?
168.
by leif 14y ago
Originally, RethinkDB was to be a MySQL storage engine, which made C++ the natural choice. They pivoted away from MySQL after my short stint in the beginning so I can't speak to why the storage code was kept (though I can't imagine it's bec
169.
by leif 14y ago
That correlation does exist, but surely it's influenced by the voting model.
170.
by leif 14y ago
It's all about what kinds of questions get discussed and addressed during campaigns. The point of the campaigning process is chiefly to elect new representation, but secondarily (and closely so) to debate and test competing theories on the
171.
by leif 14y ago
Obama's going to win. The only reason you hear pundits talking about it is because they get paid to talk about it. The media controls the messaging these days, not the candidates or the people, and it's in the media's interest to maintain
172.
by leif 14y ago
You're the coolest 15 year old. Email me (profile) when you upload, I'd love to check it out.
173.
by leif 14y ago
I was surprised too, when I learned this technique, that people weren't already doing it. I think it's just an age thing. B-trees are old so they have all the kinks worked out, at least in mature implementations. Fractal trees are new en
174.
by leif 14y ago
Is this likely to be any different from introducing a little error-correction? Also, how were we not doing this already? Also, I need a writer. Whoever wrote this up made it sound WAY cooler than when I explain error correcting codes.
175.
by leif 14y ago
Unsorted is fine, we're just counting I/Os, and it takes O(1) I/Os to read or write a buffer regardless of the layout.
176.
by leif 14y ago
Is that the same as Willard's Y-fast tree? If so, then no they're not very similar. If not then I'm unfamiliar and I should read that paper.
177.
by leif 14y ago
The argument I like goes like this: Flushing one buffer one level down costs O(1) I/Os. It moves B elements, so flushing one element one level down costs O(1/B) amortized I/Os. The tree has fanout O(1), so it has height O(log N). Therefo
178.
by leif 14y ago
I should add that, to reduce the cost of a flush by a pretty decent constant number of I/Os, you keep one buffer per child in each node. Basically, you want to do the sorting work on arrival into the node, not during the flush.
179.
by leif 14y ago
The buffers have the same capacity at each level of the tree. It doesn't have to be that way, and you can find different strategies in the literature, but that's the way we do it. The degree of each internal node is way lower, because we wa
180.
by leif 14y ago
In theory, it is cache oblivious, and the CO-DAM model informs our decisions about the implementation, but no, the implementation itself isn't actually cache oblivious. Shh, don't tell on us. A "fractal tree" is defined by our marketing te

More ›