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

111–120 of 237 posts

Re: 14,000x Speedup (2015)

#111

Post by vidarh »

neves wrote: post #58
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 a usual problem with C++ and why I hate it. There's a lot going on under the hoods, and you must be really knowledgeable of the language to prevent stupid things. Following some idioms you can really avoid it, but it is useless since your coworkers will fall into the language traps.

Knowing if you're copying or passing references is essential to understanding most languages that supports both.

It's scary how many people are unaware of it, though.

Not nearly as dramatic as the example above, but I once cut the time spent on page generation for a commercial CMS by 30% my first day in a new job by realising they did excessive new allocation of strings instead of concatenation (which will amortise the allocations by allocating more space than needed in most C++ implementations).

I find it quite disturbing, because, while I prefer to use Ruby these days, C++ documentation is really explicit about guarantees provided by both the language and the standard library with respect to things like memory behaviour and algorithmic complexity.

There's if anything less going on under the hood with C++ that you're not explicitly told about than in most modern languages.

Re: 14,000x Speedup (2015)

#112

Post by arcticbull »

qayxc wrote: post #82
arcticbull wrote: post #26

Earlier quoted context omitted.

Data structures is a weird one, it's basically a memorization class. It's the kind of thing you just have to do, a bunch of times, then it clicks. That was my experience, anyways. It's largely only relevant when interviewing, and I always cram for that like I did in college, by implementing a whole ton of data structures the week before.

> It's largely only relevant when interviewing I find the opposite to be true, but it depends entirely on what problems you work with on a daily basis. Data structures and algorithms are a toolbox and the more you know, the more options you have at your disposal to tackle a specific problem. If you work in an area that doesn't benefit much from this specific set of tools, then yes, you only it during interviews; inte…

> I find the opposite to be true, but it depends entirely on what problems you work with on a daily basis.

I suppose that's true, my perspective is as a client engineer where for the most part, someone's built the data structures for you. Yes you need to know their performance characteristics and when to use them, but otherwise if you're building them yourself you're doing something wrong. I'm sure that's not true in all roles.

> If you work in an area that doesn't benefit much from this specific set of tools, then yes, you only it during interviews; interviews done by people who don't have the faintest clue about what they're hiring you for (which is a big problem itself).

I'm actually really passionate about recruiting and improving the recruiting process anywhere I work, I'd love you to elaborate on this.

Re: 14,000x Speedup (2015)

#113

Post by andi999 »

est31 wrote: post #12
read_if_gay_ wrote: post #7

> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?

Yeah there are plenty of programs where you can tell whether they terminate or not. The proof that the halting problem is decidable has a self referential component and most programs aren't self referential like this, nor do they make any library calls to halting problem deciders :). I think it's OK to do this simlification in a simple post like this, but important to keep in mind that it's a simplification. To make…

But you can have easy examples like does the decimal reprensentation of pi contain four zeros in a row. I think we dont know if it is true, so you wouldnt know if your algo stops if you dont run it (and it stops). No need for self referential programs.

Re: 14,000x Speedup (2015)

#114

Post by andi999 »

arc0 wrote: post #77
m12k wrote: post #8

Earlier quoted context omitted.

Correct, not all programs suffer from the Halting Problem.

I think that's kind of a malformed sentence. Programs themselves do not suffer or not suffer from the halting problem, it is only a problem when considering the space of all programs.

I also think some programs can suffer from the halting problem. I mentioned above properties of the decimal reprensentation of pi (like is 123456 in pi)

Re: 14,000x Speedup (2015)

#115

Post by dumbfounder »

Al-Khwarizmi wrote: post #44
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…

The tagger's speed was probably enough for what the professor intended at the time. They probably knew how to optimize it, but didn't because they had no reason to. I say this as a professor myself, because we do that all the time in my team: we create some software system (also in NLP, by the way), we do experiments to show that it improves whatever metric we are interested in or that it teaches us something interes…

I hear what you are saying and this story is more tongue-in-cheek than trying to put down computer science or professors.

But, fyi, this tagger was not just a professor's demonstration, it was kind of ground-breaking and served as a foundation for other taggers. The professor went on to have a pretty awesome career at a few different big tech companies, far surpassing my own success. And yes, I agree, I am sure he could have made it faster himself had he dedicated the time to it.

Re: 14,000x Speedup (2015)

#116

Post by CogentHedgehog »

That's a good speedup but why are they not using locality-sensitive hashing? Or doing some basic math to convert X and Y to binned indices for a lookup table -- you can easily precompute values for a few million cells and hold them in memory. If the lookup table is small enough it would even fit in a single CPU cache, and lookup would be nearly instant. Both of these approaches provide O(1) lookup for grid cells rather than O(log n).

I used a similar optimization when I was younger to enable interactively plotting very large (at the time) 2D point datasets. We stripped out points that were so close together that the difference would not be visible. The X,Y coordinates were each binned to an integer pixel location and both were packed into a single long integer. Then we stored a hashset of longs so we knew what pixels had points occupied. When adding a point to render, we did O(1) hashtable lookups to see if the location already had a point in it. The result was an extreme speedup because we could avoid rendering all points which were not visible, and it scaled linearly with the number of points.

Re: 14,000x Speedup (2015)

#118

Post by jariel »

Software is not about writing code or optimizing algorithms.

It's about requirements, corner cases, knowing and using the right tech, and the zillion or so things that can go weird or wrong and how to elegantly handle them.

Re: 14,000x Speedup (2015)

#119

Post by jayd16 »

Al-Khwarizmi wrote: post #44
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…

The tagger's speed was probably enough for what the professor intended at the time. They probably knew how to optimize it, but didn't because they had no reason to. I say this as a professor myself, because we do that all the time in my team: we create some software system (also in NLP, by the way), we do experiments to show that it improves whatever metric we are interested in or that it teaches us something interes…

Not to mention the possibility that much of that code was written by an volunteer underclassman.

Re: 14,000x Speedup (2015)

#120

Post by andruby »

mynegation wrote: post #109
lmm wrote: post #59

Earlier quoted context omitted.

So did you measure how much of the speed improvement came from your careful memory copying tuning and how much came from the algorithmic change?

At the time, yes, but I do not have those numbers anymore. Trying my best to remember - I would estimate that the speedup of 360 / 4 = 90x is approximately: 4x multithreading (it was pretty linear speedup), 7x the algorithm and 3x the memory inefficiencies. EDIT: fixed my math, thank you andruby

Sorry to correct your math here, but going from 6 hours (6*60=360 minutes) to 4 minutes is a 90x improvement, not 900x.
Post reply on HN