c# - Branch prediction on sorted/unsorted different sized arrays -

c# - Branch prediction on sorted/unsorted different sized arrays -

i stumbled across question long ago

why processing sorted array faster unsorted array?

and wanted seek myself. had surprising results when trying different array sizes.

here's test code. (c# microsoft compiler, have not tested other languages)

static void main(string[] args) { var rand = new random(); time(rand, true, 1000, 100000); time(rand, false, 1000, 100000); time(rand, true, 1000000, 100); time(rand, false, 1000000, 100); console.readkey(true); } static void time(random rand, bool sort, int arraysize, int loopsize) { var stopwatch = new stopwatch(); var array = new int[arraysize]; array = array.convertall(array, _ => (int)(rand.nextdouble() * int.maxvalue)); if (sort) array.sort(array); stopwatch.start(); var count = 0; (var j = 0; j < loopsize; j++) (var = 0; < array.length; i++) if (array[i] > int.maxvalue / 2) count++; stopwatch.stop(); console.writeline("{0} ticks, {1}ms, sort {2}, arraysize {3}, loopsize {4}", stopwatch.elapsedticks, stopwatch.elapsedmilliseconds, sort, arraysize, loopsize); }

here's output.

614149 ticks, 262ms, sort true, arraysize 1000, loopsize 100000 630096 ticks, 269ms, sort false, arraysize 1000, loopsize 100000 634562 ticks, 271ms, sort true, arraysize 1000000, loopsize 100 1840846 ticks, 787ms, sort false, arraysize 1000000, loopsize 100

relative result timings same in release vs. debug mode (with debug beingness twice slow).

the lastly 2 results, me, create sense. follows logic of question linked above , sorted 1 runs faster due assume branch prediction. first 2 results, however, i'm confused by. why same time? also, why not faster lastly two? think smaller array cause in closer cache , hence whole thing runs faster. (loop size * array size = constant between first 2 , lastly two, same number of inner iterations)

c# branch-prediction