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

When Big O Fools You

jackmott.github.io

Post reply on HN
Print view View original

111–120 of 134 posts

Re: When Big O Fools You

#111

Post by andrewflnr »

hinkley wrote: post #99
gens wrote: post #57

Earlier quoted context omitted.

Can't you just imagine it is reversed, where the_array[num_things-1] is the first ?

The awful thing about writing benchmarks is that if you don't give the worst case example, people give you shit for coming up with metrics that say whatever you want to say. If you give metrics for the case that should be worst for your argument, people give you shit about using such a stupid example. There's no way to avoid someone giving you grief no matter what you do.

Um, give both?

Re: When Big O Fools You

#112

Post by vonmoltke »

mannykannot wrote: post #107
vonmoltke wrote: post #58

Earlier quoted context omitted.

> the scientific method requires a hypothesis to test for measurements to be meaningful That's the simplistic grade school version. In practice, characterization and measurement is part of a feedback cycle that is used to develop and refine hypotheses. Experiments need a hypothesis to test, but measurements do not require experiments. Where the "measure, test" crowd usually goes off the rails is in not entering that…

I am not buying your distinction between measurements and experiments - experiments are measurements with a purpose. You don't have to start with measurements. You can often do some analysis before you have anything to test, and that may save you a lot of time measuring, testing and tinkering with something that doesn't have a prayer of working. If you are measuring the environment that the system will interact with,…

> I am not buying your distinction between measurements and experiments - experiments are measurements with a purpose.

I'm not making one. I'm saying that measurements don't require an experiment to be meaningful.

> You don't have to start with measurements.

I didn't say you did, I said you can. The person I was responding to claimed otherwise.

> There's a curious anti-intellectualism in software development that is opposed to any suggestion that thinking about problems is useful. It seems to go hand-in-hand with a simplistic world view that only sees dichotomies, together with the assumption that there can only be one answer.

As someone who constantly rails at the lack of engineering rigor in software "engineering", I agree completely.

Re: When Big O Fools You

#113

Post by vonmoltke »

_benedict wrote: post #96
vonmoltke wrote: post #58

Earlier quoted context omitted.

> the scientific method requires a hypothesis to test for measurements to be meaningful That's the simplistic grade school version. In practice, characterization and measurement is part of a feedback cycle that is used to develop and refine hypotheses. Experiments need a hypothesis to test, but measurements do not require experiments. Where the "measure, test" crowd usually goes off the rails is in not entering that…

I deleted from my comment an explicit calling out of this feedback loop, as it was implied, I thought, by the statement that the measurement and testing were both important, but of limited value by themselves. However I disagree that measurements have any meaning unless they are conducted as experiments, or potentially as exploratory work looking for an experiment to conduct. Even such exploratory work needs to be dr…

> However I disagree that measurements have any meaning unless they are conducted as experiments, or potentially as exploratory work looking for an experiment to conduct. Even such exploratory work needs to be driven by at least the loosest of hypotheses, since measuring everything is infeasible. So this is just as much an experiment, just one you don't have a high expectation of predicting the outcome of.

> Either way, this recognition of the necessity of at least a minimal hypothesis in all of these scenarios is typically lacking is my fundamental point.

That's an overly broad definition of hypothesis that results in every decision-making process fitting the model. Even the "measure, test" people you were complaining about have that. They formulate a "minimal hypothesis", take measurements, fix what they see, and call it a day. What they don't do is iterate on the process and get down to the root causes.

Furthermore, in some closed systems measuring everything (at some level of granularity) is feasible. It leads to a troubleshooting cycle of continuously focusing the measurement towards an indeterminate point, with the specific point being the answer. This kind of fault isolation is much more productive, in general, than continuously developing and testing hypotheses about what specific things might be an issue.

Re: When Big O Fools You

#114

Post by dingo_bat »

ctvo wrote: post #2

If the author sees this: please consider changing your color choices. It'd make reading the content you put so much work into producing easier for everyone. I couldn't finish the post. The 90s hacker's lair colors were that offensive.

I like the colors a lot. Much easier on the eyes than blinding white with gray text.

Re: When Big O Fools You

#115

Post by Retra »

johncolanduoni wrote: post #106
stcredzero wrote: post #28

Make Sure the Abstraction is Worth It Yes! All abstraction has a price. This is what people really mean when "all abstractions leak." Basically, all code and runtime features have a cost in terms of developer resources, cpu, memory, etc. The "inner game" of development isn't being able to muster huge amounts of "cleverness" power. The "inner game" is being able to put whatever resources you have to the best possible…

This isn't true at all. What's the cost in developer resources, cpu, or memory of making a complex number class in C++ a template over floats and doubles? How about the cost of using Rust's generics to make a parser that can parse from any linear source of bytes (e.g. both files and in memory byte arrays)? There's plenty of abstractions which don't actually cost anything, and there's room for even more.

What's the cost in making a template more generic? Greater compile time. Need for compiler that can handle generics. Greater number of functions in binaries, and thus more unique places for bugs to occur. Dynamic library bloat. Harder to understand code. Quirky edge cases. Harder to learn languages. Harder to parse languages. And of course, developer time is spent dealing with all of this.

Abstractions leak because they are models, and thus are necessarily different from the concrete things that they model. These differences can and will cause problems. Generic programming is an abstraction that pretends you aren't working on low-level un-typed system. And you pay for that abstraction any time you need to deal with low-level demands through that abstraction.

Re: When Big O Fools You

#116

Post by hinkley »

andrewflnr wrote: post #111
hinkley wrote: post #99

Earlier quoted context omitted.

The awful thing about writing benchmarks is that if you don't give the worst case example, people give you shit for coming up with metrics that say whatever you want to say. If you give metrics for the case that should be worst for your argument, people give you shit about using such a stupid example. There's no way to avoid someone giving you grief no matter what you do.

Um, give both?

Then both groups agree that your examples are terrible ;)

Re: When Big O Fools You

#118

Post by brianwawok »

firethief wrote: post #71
mezuzza wrote: post #32

Earlier quoted context omitted.

This point should be understood very clearly: The article isn't wrong that an ArrayList has O(n) for a single insertion. However, the article misses that amortized analysis shows that the same structure can be made to have O(n) for n insertions as well. In effect, ArrayLists can be thought to have O(1) insertion time in practice meaning that all you are comparing are the differences in constants between the two struc…

Isn't that an argument for average case performance being a better predictor of average cases than worst case performance?

Well except quick sorts worst case is very easy to hit. Hence why you don't use it in CS101 form.

Re: When Big O Fools You

#119

Post by jwatte »

One thing I didn't see in the article: in addition to cache misses, the list stores 3 words per word; the array between 1 and 2 (up to 3 only when reallocating,) so array touches less RAM, even when inserting.

Re: When Big O Fools You

#120

Post by jwatte »

gingerrr wrote: post #80
justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

Would be interesting to see the performance of Python's overallocation algo compared to a simpler one like Lua's, which just overallocates to the next power of 2 (so if you have a list with 4 items and want to add, it jumps to 8, then 16, then 32). I can't imagine the bitwise operations adding up to that much time added in Python, but Lua needs to increase size much less the larger the list (after 7 iterations Lua ha…

Even with only 25% growth per realloc, you hit logarithmic overhead (only with a higher k because more actual copying.)
Post reply on HN