Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

14,000x Speedup (2015)

james.hiebert.name

Post reply on HN
Print view View original

201–210 of 237 posts

Re: 14,000x Speedup (2015)

#201

Post by EmbarrassedFuel »

sdenton4 wrote: post #191
mynegation wrote: post #39

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each…

Meanwhile, there's a perception that machine learning is hardware-bound for speed increases, which just isn't true. I work on a pretty heavy ML system, which a year ago took about a month to 'fully' train. Today we're down to 25 hours training time using the same hardware, based mostly on improvements to the model. The improvements are coming from a combination of signal processing tricks and tricksy model changes. I…

Sounds interesting, would you be able to share anything about the signal processing tricks?

Re: 14,000x Speedup (2015)

#202

Post by tome »

not2b wrote: post #196
andi999 wrote: post #170

Earlier quoted context omitted.

Vtable and vtable pointer is under the hood.

Yes, but any C++ programmer who expects to be hired will have a good understanding of vtables and vtable pointers. They are a lot less tricky to reason about than, say, thunks in Haskell.

What makes you so sure about that?

Re: 14,000x Speedup (2015)

#203

Post by fwip »

8ytecoder wrote: post #134
mynegation wrote: post #39

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each…

This is at the very least a clever and involved optimization. Let me tell you the story of my similar 10h to 10min fix. We had this cronjob that was supposed to run every hour, detect all changes to the customers and related table and sync with the marketing saas tool. It was written in Rails and took 10 mins at first. As we grew the time taken by this job also grew linearly. To a point where it took 10 hours and we…

My first big win came as an intern, when I reduced the big O complexity of an algorithm written by a (very smart) statistician for our paper to O(n^2) instead of O(n^4). This was just driven by realizing that a couple data lookups in an inner loop were themselves O(n^2).

If I recall correctly, that raised the "feasible" value of K from about 4 to about 14 on the hardware at the time, which was more than enough for our purposes. I wanted to keep optimizing, but my boss correctly reminded me that shipping the paper was more important.

Re: 14,000x Speedup (2015)

#204

Post by pmiller2 »

cyphar wrote: post #102
arethuza wrote: post #96

Earlier quoted context omitted.

Isn't that already built into the definition of O? "f(x) ∈ O(g(x)) as there exists c > 0 and x0 such that f(x) ≤ cg(x) whenever x ≥ x0" Saying f(x) is O(g(x)) doesn't say anything about how those two functions compare below x0? https://en.wikipedia.org/wiki/Big_O_notation Edit: Not trying to be snarky - just trying to check whether my 30+ year old memory of education on such matters is even vaguely correct... :-) Edi…

You are correct, the point being made was that a lot of people aren't aware of that and just take it as gospel that O(1) algorithms must be faster than O(n) ones -- but, as you said, big-O notation only says that is true after n goes above some threshold n0 which may be (and usually is) very large. After all, the most efficient (in terms of big-O) known algorithm for multiplying two numbers uses a 1729-dimensional Fo…

Interesting (coincidental?) appearance of 1729 here in a numerical algorithm.

Re: 14,000x Speedup (2015)

#205

Post by karmakaze »

tetha wrote: post #168
8ytecoder wrote: post #134

Earlier quoted context omitted.

This is at the very least a clever and involved optimization. Let me tell you the story of my similar 10h to 10min fix. We had this cronjob that was supposed to run every hour, detect all changes to the customers and related table and sync with the marketing saas tool. It was written in Rails and took 10 mins at first. As we grew the time taken by this job also grew linearly. To a point where it took 10 hours and we…

This is when being the guy knowing a few database tricks is fun. We had one reporting query that ran for 13 hours or so, in a normal web request. Not very successful, but it tried its best. Running this through explain while thinking of daloks revealed some dependent subqueries. Those are the devil in mysql because they are evaluated per row in the outer query. That takes a lot of time very quickly. Eventually we wra…

Saw one of these recently in a query that was ported from PostgreSQL to MySQL. Same thing join-with table-expression to fix it from 6+ hours to seconds. MySQL will sometimes consider a subquery to be 'dependent' even when there are actually no dependent terms and could have been evaluated once.

Re: 14,000x Speedup (2015)

#206

Post by karmakaze »

kadoban wrote: post #149
hinkley wrote: post #144

Earlier quoted context omitted.

I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are d…

I'd argue that none of that is the hardest part of programming, or at least what I'd focus on in terms of what comes up the most and what effects users and developers and suits the most. Judging by those, the most important hard parts are around planning and estimating work, and correctly understanding when those make no sense, and in validating code for correctness, especially over time. If we ignore importance and…

The real problem with naming things is that the wrong 'things' have been isolated, if there was a clear understanding of what was being isolated and why the naming part would be easy(er).

Re: 14,000x Speedup (2015)

#208

Post by dang »

danielvf wrote: post #199
dang wrote: post #166

Earlier quoted context omitted.

Please post your improved and correct perspectives without name-calling. Doing otherwise makes the community worse, even if you're right. https://news.ycombinator.com/newsguidelines.html

My apologies. While I don't see the name-calling towards an individual, my previous post did mention possible bad faith, and I would not been glad to have my post written about my code. I also slightly misunderstood what the author's code was doing. I can see how it is not conducive to helpful discussion. The author optimized their code in a way that was fast enough, and fast enough to massively change the entire bus…

Appreciated!

Re: 14,000x Speedup (2015)

#209

Post by zimpenfish »

lmilcin wrote: post #56
dumbfounder wrote: post #16

Computer Science for the... loss? I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US…

So one of the applications I have worked with was an embedded credit card terminal app which needed a transactional database. Since I could not find a product that would fit all requirements I decided to write one. Now, you can imagine smart algorithms, trees, hashes... Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all…

> I got into many heated discussions with "computer scientists" in the team.

Had a week long argument once about an (relatively) inefficient MySQL query because "it's not going to work for 1000 things" when a) we had barely 10 things currently running and b) the customer was >this far< from cancelling because stuff wasn't working (which this query would help with.) It was a frustrating time. I think there's a lot of developers who "know the price of everything and the value of nothing".

Re: 14,000x Speedup (2015)

#210

Post by zimpenfish »

leeter wrote: post #153
lmilcin wrote: post #56

Earlier quoted context omitted.

So one of the applications I have worked with was an embedded credit card terminal app which needed a transactional database. Since I could not find a product that would fit all requirements I decided to write one. Now, you can imagine smart algorithms, trees, hashes... Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all…

People forget that Big O is only part of the story, they also need to consider Little o and average runtime. Just because something is n^2 or worse asymptotically doesn't mean the average runtime will be that bad. There are many cases where the average runtime is closer to Little o almost all the time.

> they also need to consider Little o and average runtime.

Frequency of run is also important - a batch job that takes 5 hours that only runs once a month? Is it worth optimising that?

Post reply on HN