HNHacker News
TopNewBestAskShowJobs

dhruvbird

838 karma · joined April 2, 2010

Copy this into your address bar and press "enter" to visit my home page:

javascript:window.location="http://"+window.location.search.match(/id=(\S+)/)[1]+".com"

submissionscomments
dhruvbird··on Don Knuth releases Volume 4, Pre-fascicle 6A [gzipped ps]
Fixed
dhruvbird··on Show HN: Use DuckDuckGo for !bangs and Google for everything else
From what I understand, all of this can be done entirely in javascript, mitigating any security issues of queries going over the wire.
dhruvbird··on Varnish author criticizing HTTP/2.0 proposals
Excellent judge of the protocol. It's interesting that no one is trying to solve the cookie bloat problem with http.
dhruvbird··on My Senior Design Project: Node.js WiFi-Extending Robot
I guess there are some interesting results as a result of this effort:

* Javascript can be used to program these things and is quite capable of handling low-level kind of stuff

* Since it's easier to write js code than c/c++ code (for me), I would personally prefer it; assuming that the performance degradation is within allowable limits

dhruvbird··on My Senior Design Project: Node.js WiFi-Extending Robot
Love the idea of dropping repeaters and back-tracking if the wi-fi connection is lost. I guess you could also extend it to remember where the repeaters were dropped and try to navigate to one of these spots if the backtracking fails (imaging some debris coming in the way after the robot has moved ahead, making backtracking impossible).
dhruvbird··on Reading Between the Benchmarks: How MemSQL Designs for Speed and Durability
@Ankur - Thanks again for the clarification - that's helpful information.
dhruvbird··on Reading Between the Benchmarks: How MemSQL Designs for Speed and Durability
Thanks Ankur for the details!

I saw you mention in another comment that memsql stores almost 30x the (rows) data as mysql by the end of the experiment. I would be curious to know why this is so, and what that data is.

Also, from what I understand after reading the paper, the lock-free skip-list node is pretty heavy (more than the 3~4 pointers that a naive implementation would use). What is the # of bytes it occupies in memory. Assume that the data field is just a pointer (8 bytes).

Curious: Do you always store the data as a pointer or does it get stored inline for smaller types?

dhruvbird··on Reading Between the Benchmarks: How MemSQL Designs for Speed and Durability
A few questions Ankur:

1. How many rows were actually present in the tables (in all)?

2. What did the VSZ and RSS for mysqld and memsqld(?) look like at peak and after benchmarking was completed?

3. What did the CPU usage of each mysqld and memsqld(?) look like at peak and what was the total amount of processor time used by each database?

4. As a percentage, how many statements were inserts and how many were queries - am guessing I might be able to get an idea my looking at the code, but it's easier to ask - esp. since you'll know more about the code.

5. AUTOCOMMIT ON or OFF? (dunno what the defaults are).

dhruvbird··on MySQL is bazillion times faster than MemSQL
Actually, there are papers about it http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.4... but I don't know much about the implementation complexity since I've never implemented one.
dhruvbird··on MySQL is bazillion times faster than MemSQL
@nikita I see: http://developers.memsql.com/docs/1b/faq.html#does-this-mean...

Do you mean you determine placeholders without actually parsing the SQL?

@jakejake The docs. seem to suggest that the benefits of prepared statements are won without using prepared statements in MemSQL.

dhruvbird··on MySQL is bazillion times faster than MemSQL
I agree with what you have to say, but I don't see how you can determine that this query:

SELECT * FROM table WHERE id > 5 LIMIT 10;

is actually of the same form as this query:

SELECT * FROM table WHERE id > 10 LIMIT 5;

without actually parsing the two. I mean you will incur a parsing overhead either way. What I think MemSQL is trying to optimize out is the actual execution of the query. I mean rather than interpreting and running it with checks performed in every iteration, they are compiling the code. I don't know how much of a difference this would make without actually seeing the numbers.

dhruvbird··on MySQL is bazillion times faster than MemSQL
Even though skip-lists as described in literature are singly linked (horizontally), they can be augmented with a back pointer to make them doubly linked. This would allow one to re-use an index as either a forward or backward index, and the order of the index is no longer important. I am not sure how easy this is to do in a lock free fashion. However, if one were to adopt a strategy which combines functional data structures and RCU, I am guessing that it would be possible to implement it with relatively good readability.

Additionally, skip-lists can be used for performing range queries as well. This means that "SELECT * FROM table ORDER BY id DESC LIMIT 5;" can be executed very efficiently as long as there is a skip-list on "id". Additionally, even COUNT(), MAX(), MIN(), etc... queries can be optimized in a similar fashion. Again, however, doing it in a lock-free manner might not be the most fun thing to do.

dhruvbird··on JQuery knobs
fuckin awesome!!
dhruvbird··on O(n) algorithm to find longest palindromic substring w/o suffix trees
I should thank you for the brilliantly written article. All the claims have been mentioned clearly, and the reasoning strung together in a coherent manner.

I agree with the fact that getting the optimization isn't intuitive, but the basic O(n^2) on which the idea is based is almost trivial.

dhruvbird··on O(n) algorithm to find longest palindromic substring w/o suffix trees
substring is not subsequence in the context of this problem
dhruvbird··on O(n) algorithm to find longest palindromic substring w/o suffix trees
Nope, see the section "A simple asymptotically optimal solution" - it doesn't use Suffix Arrays.
dhruvbird··on Why we didn't use a bloom filter
Is this guy serious or joking?

"Have you ever used the STL? I did for about 6 months professionally, and I'm glad that I could go back to C and Python. More seriously, object orientation in C++ doesn't come for free. Aside from the pain of the syntax of using C++ templates (and difficult to parse error messages), all of that object orientation hides the complexity of method dispatch in what are known as vtables."

Seriously?

1. Python is faster than C++?

2. All OO features (method invocations) in C++ use the vtable?

IMHO, just using the right iterator abstraction and using the STL algorithms should be within performance limits.

dhruvbird··on Many times faster (de)compression using multiple processors.
This is awesome since compression in parallel has been largely neglected in practice.
dhruvbird··on Sometimes the bug isn't in your code, it's in the CPU
wow! this is quite a rare thing...
dhruvbird··on A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
Sorry about the pay-wall link guys :-( I'm in university so I didn't realize it was this way.

I've posted 3 other links which should allow free access to the paper. I think these things should be open (and free) to start off with.

dhruvbird··on A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
I agree. I too keep wondering "why?"
dhruvbird··on A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
Google Cache Link: https://docs.google.com/viewer?a=v&q=cache:n-YwxuJHeAoJ:...
dhruvbird··on A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
Or you can try this one if neither work: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.1...
dhruvbird··on A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
Does this link work? http://www.deepdyve.com/lp/association-for-computing-machine...
dhruvbird··on The shutdown of library.nu
Which is why I really like what Zed Shaw is doing and I hope his series extends to "Learning X The Hard Way", where 'X' can be anything. http://learncodethehardway.org/
dhruvbird··on The shutdown of library.nu
We do have something called "Indian Low Price Edition" http://duckduckgo.com/?q=%22indian+subcontinent%22+%22low+pr... but not all titles are available for whatever reason. Mostly, these are books used as texts in schools & colleges.

Another note: An LPE of a book that is available for INR ~500 would cost anywhere from INR ~4000 to ~6000 if the original publication is ordered. Generally the original is not stocked so there is a wait period of ~5 weeks from placing the order.

dhruvbird··on Ask HN: How to move away from Gmail
An email is exchanged between >=2 people. One of them securing their account has little (if any) effect on privacy.
dhruvbird··on Advanced Data Structures MIT
That's just sheer excitement!!
dhruvbird··on Advanced Data Structures MIT
VIDEO LECTURESSSSS!!!!!!!!!!!!!!!!!!!!!!!!!! http://courses.csail.mit.edu/6.851/spring12/lectures/L01.htm...
dhruvbird··on SSTable and Log Structured Storage: LevelDB
Is it not possible to re-write a B-Tree once it doubles in size?

For example, suppose you start off with a B-Tree with size 1000. Once it reaches 2000, re-write it. This way, the query performance remains good. Next time it reaches 4000, re-write it again, then at 8000, and so on... This way, you get good query speeds even in the presence of random inserts.

You need not re-write the B-Tree on the 2000'th or 4000'th insert. Instead, you can start the re-writing process when the size of the B-Tree reaches O(n/log n). This way, for the last O(log n) values, every time one value is inserted, we copy O(log n) values from the old tree to the new one. When we are done, we have an almost sorted list of values that we inserted in the new B-Tree!

← PreviousPage 3 of 5Next →