Hacker News Reader

Comment by skybrian | Hacker News Reader

I think you're sweeping an important distinction under the rug.

If every major language provides an O(n log n) sort function, is it still a leaky abstraction? I'd say no. You can use it without worrying much about the details.

But it sounds like the situation with back-propagation is different, since the internal details of the algorithm affect whether you get a usable answer at all.

A borderline case might be something like a SQL database, where in theory, creating an index shouldn't change query results, but in practice, the performance can change so much that it effectively does.

Unlike with back-propagation, you can tune database performance without worrying about queries returning different results (assuming they don't time out). So it's still a useful guarantee.

View on HN

Speaking from experience, I've had to worry about what implementation of sort is being used in many languages, from Java to C++, even Go and Python.

There are a lot of details to get right: how are elements compared? Is the sort stable? Is it efficient for small N? Is it efficient for nearly-sorted arrays? Is it efficient when almost all the elements compare equal? Is it guaranteed O(n log n) or average? If average, is there an input that reliably triggers n^2 behavior making it a DDoS vector?

Anything is a leaky abstraction when you care enough.

Those properties should ideally be part of the documentation so that the abstraction stops leaking.

One could argue that if these details are necessary for correct/performant operation, then it is a leaky abstraction.

To me a leaky abstraction is an abstraction that does not expose all the relevant details. So if those details are written on the spec sheet of the black box then there is no leak.

If the box is only labelled with O(nlog n) without specifying constants then there is a leak.

I feel that if you care that much about the internals of the abstraction then you don't necessarily want an abstraction anymore, but rather the concrete thing that is being abstracted over. I think abstraction is an admirable quality that has numerous advantages, but if you need guarantees on the properties of what's under the abstraction then an abstraction is probably not what's needed at that point.

Except that for nontrivial use cases, the many different nlogn sort algorithms have trade offs which matter. A friend just wrote his own sort implementation optimized to maximize cache hits, because of certain quirks of his data that he knows ahead of time.

In much the same way, much of the interesting work with machine learning requires deep specialist knowledge in which selecting the best approach requires digging beneath the abstraction. Many specific applications have their own quirks, which is where significant gains are often made. (To be honest, I think the last year was more exciting for the advances in applied ML than in theoretical work.)

A co-worker wrote a library for distributed training of DNNs for a specialized use case. Because of certain quirks of our use case (think sparsity and consistent patterns in the data), there were certain optimizations he could make to the training process that gave nice linear scaling in the number of training nodes.

What is O(n log n)? Time complexity? What about memory requirement? Last month I decreased memory requirement from 16GB to 100MB in one implementation of a "stable&fast" algorithm. Really, using a function just because it's O(n log n) without understanding its characteristic is like a blind surgeon randomly amputating limbs because maybe it will help. But that's fine for me, I have more work then, fixing software bugs made by incompetent* programmers is quite nice.

*incompetent - those who think they know something and are not willing to learn anything new

Why do you assume the commenter doesn't understand the time and memory characteristics of quicksort?

Nobody mentioned quicksort. You're assuming quicksort, which is what the issue is. Many languages don't actually use quicksort, fyi. The practical performance considerations of just quicksort itself also change depending on how you've implemented the small details - are you moving memory around, or just changing pointers? Huge difference in the real world, no difference in the algorithm.

I oversimplified my response and it lost the point I was making. You are certainly correct that many languages don't use quicksort. My bad.

I was responding to a comment that I felt was needlessly dismissive. The default sort algorithm of any major language's standard library is usually not worth trying to beat, and calling someone "incompetent" for not reinventing the wheel each time they encounter data that needs to be sorted is absurd. Note: I said "usually", not "never". A competent programmer doesn't fix problems that don't exist, and you would absolutely have to profile code before convincing me that the choice of sorting algorithm was the source of a performance problem.

As far as the details go... In only a few languages (e.g. C) might you really even consider moving memory around rather than pointers. The semantics of standard library sort in Java, C#, Ruby, Python, Javascript... is sorting an array of primitives by value or objects by reference.

There is no quicksort mentioned.

> What is O(n log n)? Time complexity?

And then worst case? Best case? Average case? Which applies to random input? Nearly-sorted input? What's the overhead for a "short sort", can/should I use this to sort small sequences in a tight-ish loop or is it only for large sequences?

And then worst case? Best case? Average case?

I was under the illusion that Big-O was always asymptotic complexity (ie worst case) and that other notations (little-o, big-omega, big-thetha etc) were used for best/average/etc case. Perhaps I'm wrong, however.

Which applies to random input? Nearly-sorted input? What's the overhead for a "short sort", can/should I use this to sort small sequences in a tight-ish loop or is it only for large sequences?

Indeed. The details matter.

My favourite example is how a naive linear search can perform better than a non-linear search with a better (in O() terms) algorithm if, for example, the linear search can do most of its work in cache (eg small input sizes or otherwise regular access patterns (predictable for prefetch)).

> I was under the illusion that Big-O was always asymptotic complexity (ie worst case) and that other notations (little-o, big-omega, big-thetha etc) were used for best/average/etc case. Perhaps I'm wrong, however.

No, asymptotic notation only refers to the behaviour of the function (or algorithm) as you take the limit N->inf, e.g. changes to the size of the input. But the nature of the input often changes the behavior as well.

Thanks for the correction!

You can have Big-O of worst case and Big-O of average case. "Asymptotic complexity" itself does not imply worst case; the assumptions you make to construct the function itself determine worst case or average case.

> If every major language provides an O(n log n) sort function, is it still a leaky abstraction? I'd say no.

Great example :) You get different results if you use merge sort or quicksort.

The former is stable; the latter is not.

Okay...so you can be more specific with your API and specify whether stability is guaranteed. Eventually you can be specific enough that you essentially characterize the implementation.

> If every major language provides an O(n log n) sort function, is it still a leaky abstraction?

Yes, if the performance is still not acceptable and you look into the problem and discover that your scenario could benefit from radix sort, or one of partial sorting, or some kind of intermittent sorting, all of which would require investigating the specific case at a "white box" level, ignoring the existence of a black-box O(n-log-n) sort API call.

The implementation is a black box but the performance characteristics could very well be part of the API contract. When you require and it's feasible to use radix sort you probably know not to use the standard sort function.

Yes, but reasoning about the API contract is exactly what being taught sorting algorithms helps you navigate, just like learning the guts of backprop helps the ML practitioner understand why things can go wrong.

> You can use it without worrying much about the details.

I invite you to start sorting data which is often already sorted (or often all identical) and tell me you didn't need to worry about the details.

Perhaps the distinction would be between things that are "fundamentally a heuristic with some math behind it" versus things are "mostly theoretically settled with some corner cases you have to worry about"

And neural networks using backpropagation to minimize an error function are definitely the former while the "go to" techniques of mathematics are generally the latter.

I think this is generally acknowledged, in fact.

Sooo it seems logical that students of these modern machine learning techniques should be impelled to "get their hands dirty" with the numericals processes involved since this will add to the data they use to drive the intuitions which allow them to avoid the multiple pitfalls of neural networks.

Reply on news.ycombinator.com