Looking at big-O isn't very informative. We have plenty of statistical tools for telling whether there is an effect even with noisy data.

▲

xlii 4 hours ago | parent | next [-]

I ran 10k test locally on 2e5 and I'm seeing 4 orders of magnitude instability, but very high local stability (i.e. runs within specific second are very stable, showing almost no deviation, runs couple second later are the same, but results are within 1 OoM of the prior results (smaller batches, 500 tests).

I'm not saying that optimization isn't valid, what I'm saying is that Quicksort shouldn't be optimized over randomized per run data set.

▲

marginalia_nu 4 hours ago | parent [-]

You don't happen to be running `srand(time(0))`?

> I'm not saying that optimization isn't valid, what I'm saying is that Quicksort shouldn't be optimized over randomized per run data set.

But yeah, this is correct. When optimizing, we want to pin every variable other than the change, as much as possible.

	▲	atn34 3 hours ago \| parent [-]
		Then you run the risk of overfitting to whatever seed you picked. I think fixing a seed is probably a good idea most of the time but it’s worth considering

▲

cogman10 4 hours ago | parent | prev [-]

It's a good rule of thumb that can be quite useful without additional analysis. It's not always the right way to do performance tuning, but I can't count the number of times I've changed an O(n^3) to an O(n) and seen massive performance gains as a result.

▲

marginalia_nu 4 hours ago | parent [-]

Yeah it helps make awful code decent, and some algorithms are better than others, but in terms of high performance code, locality, vectorization, and branching often matter much more big O.

▲

bluGill 2 hours ago | parent | next [-]

That depends on what end ends. For a small N, very bad algorithms can still be plenty fast. Sometimes it can even be faster. Some of your lower O algorithms can have very terrible constant factors, which means they're terrible when N is small, but as N gets large.

Big and small N different for different algorithms and hardware both.

▲

cogman10 3 hours ago | parent | prev [-]

Totally agree, but I'm in Java land and cursed to have about the worst case scenario for those things :D

▲

marginalia_nu 3 hours ago | parent [-]

Oh yeah I'm also mostly in Java land. These concerns are also concerns in Java, plus whatever C2 gets up to.

	▲	cogman10 3 hours ago \| parent [-]
		Valhalla can't come soon enough. I've definitely had to change things into SOA in order to eke out performance. My coworkers aren't thrilled seeing `double[] x; double[] y;` but that really is about the only way to get the JVM to play nice.