last day (31 days later) » 

1:07 PM
6
Q: Optimize this function (in C++)

Jakub M.I have a cpu-consuming code, where some function with a loop is executed many times. Every optimization in this loop brings noticeable performance gain. Question: How would you optimize this loop (there is not much more to optimize though...)? void theloop(int64_t in[], int64_t out[], size_t N) ...

 
@jalf: I expected it because I can iterate pointers directly, instead of iterating a variable and adding it to the base pointer
@MatthieuM.: I am afraid I don't get your question, but N is the of in and out size, so after N you have only seg fault
@MatthieuM.: the input is random
 
@JakubM. the unfolded loop is off by one (it also assumes that N%CHUNK==0 but that is probably ok); It should be for (size_t i = 0 ; i < N; i+=CHUNK)
 
@sehe: thanks, this i=1 is correct for the original algorithm, although for this example it does not make sense : )
 
@JakubM. are you sure it does when doing the unrolled version? It will loop while i<N and dereferences in[i+3] inside the body; this will read in[N] eventually, which is out of array bounds.
 
@sehe: i=1 in the original one makes sense, believe me : ) here, rather not, it is a minor detail
 
1:07 PM
@JakubM.: ... I don't get it. I never said i=1 was wrong in the original version. If you agree that it is off-by-1 in the unrolled version, could you not just edit the question to fix it?
 
1:35 PM
Hi Jakub, what would you say if I have found a version that uses a heuristic optimization that, for random data distributed uniformly will result in ~4.3x speed increase for floating point, and ~(to measure on average) for int64_t speedup?
Of course, I'm using the same test-bed code to verify that the results are correct and exactly match the original implementation from your OP
Ah, the average timings are in (average across 20 different random inputs):
total time in OP algorithm: 117250 msecs
total time in Spiffy algorithm: 36278 msecs
speedup factor: 3.23199 x
I'll clean it up some more, but barring some input characteristics, I think you'll have a winner here.
 
1:54 PM
Oh, by the way, the float speedup is relative to your original algorithm on floats as well, not on int64_t. Otherwise, the performance gain is bigger still, namely 117250÷11100 =~ 10.56x speedup
 
2:04 PM
This is still measuring uniform distributions. A 'worstcase' load of int64_t uniformly in the range [-100,15) (i.e.: negative numbers in input are 6x more likely to occur than positive numbers, i.e. 87%)
... there is a speed loss (execution time increases by a factor of 1.17x (not too bad, perhaps?)
 
2:18 PM
... The same 'worstcase' bias applied to floats results in a slowdown of 3.4x though. So it looks like you should use floats only to amplify performance gains iff you know you'll have them.
 
2:33 PM
[Btw, using doubles has worse performance than floats.]
 
2:49 PM
"what would you say if I have found a version that uses a heuristic optimization that, for random data distributed uniformly will result..." well, I would say: great ! : ) what do you mean heuristic optimization? you mean: apply different optimizations depending on the sructure of the data?
 
What I have now is basically this: it is a single threaded, sequential forward scan, but with lookahead.
It uses the lookahead to see that a a subrange is safe for 'straight' cumulative summing
When unsafe numbers arrive (in fact, I could be smarter than that, but right now it means, whenever the input is negative), I switch to the 'complicated' loop, ...
... and I automatically switch back to lookahead once both max and the current input value get positive. This is why all negative input wouldn't improve, and (pos,neg,pos,neg,pos,neg....) input would be really worst case
(you'd only get extra checking, reduced pipelining and reduced cachelocality)
I'm trying to a best-case scenario in a few minutes (all-positive data). I'm curious what to expect from that. (I had been sidetracked trying to squeeze more performance out of the float version over the last half hour)
Woah... that's not really fair, but simply substituting uint6t for int64_t results in
total time in OP algorithm: 101097 msecs
total time in Spiffy algorithm: 60 msecs
speedup factor: 1684.95 x
without any further changes. Now let me do the inverse test: testing with only negative values. This should stay in the 'old style' state of the loop, and will cost a bit due to the added checks, but probably not insane
Here it is (another blatant synthetic, meaningless benchmark):
total time in OP algorithm: 99878 msecs
total time in Spiffy algorithm: 140107 msecs
speedup factor: 0.712869 x
Synthethic but it does allow you to reason about the extremes as far as this hueristic is concerned
 
3:24 PM
The boost is really impressive. Let me ensure I understand it well: For an input vector IN[] you: 1) scan IN[] to check if a range is "safe" for(i =last_i ... i++) { if safe( IN[i+1] ) {...} else {break}} 2) process range IN[last_i ... i]` as "safe cumulative max"
 
I can show you the code, but I'd push it over the other gist
Ah, better idea, let me just add the optimized version alongside, that way you can see how I wrote it.
 
Cool, I am really curious about that
 
Like I just said to @MatthieuM there is certainly room for (minor) perfection, I suppose I could make it hurt less for absolute worst case (either by making the stop condition for the 'original' branch of the algorithm less heavy or by 'learning' along the way (learning that the stretches of 'safe' data are too short, and just sticking with the dull old approach for the rest of the call
 
did you also tried memory alignments?
 
@JakubM Nope
Also, right now, I'm really 'dumb' with what is considered 'safe data'. I could

* make the return to safe condition smarter
* make the runs in either state have minimum length (however, this could hide shorter patches of safe data, but helps unfolding; you could manually unfold a stretch there and have best of both worlds, presumably)
Ok, posting the code in a jiffy
 
3:38 PM
where?
 
on github, I'll post a link of course
 
("in a jiffy" I think I just learned a new expression :)
 
earned? learned
jiffies are variable length for me today since I'm having the kids and they are a bit demanding today :0
 
give them some algorithm to optimize
 
@JakubM ROTFL
will there ever be a day? (they're 3yrs and 5 yrs right now. Bit timely to start with turtle graphics :))
hope you noticed the link
It is still a bit raw, but I tried to change all the identifiers (you know the ones that start out as 'spiffy', or just ten commented versions of the uniform distribution constructor :)) into something more meaningfull
 
4:09 PM
thanks! i am just reading it
 
4:31 PM
very nice! i think i learned a lot today. thanks again
 
4:46 PM
by the way, would you mind explaining bit more what do you mean by "return to safe condition smarter" and "runs in either state have minimum length"?
 
yup. The best way to show you is in code. But really, the best way would be to profile with real life data. Is you data strictly random? (obvious answer: no, because what would be the use analyzing it?) If not, can you say it is mostly positive? Can you say it is highly singular or is it semi-linear (is it a curve? or are there many erratic jumps?)
it is basically about avoiding state switching. There are two logical states: the loopify stage (which eats unsafe elements until max becomes 'regular' again) and the lookahead/fastforward stage (i.e. find_if+transform) which eats the next 'sage' region
If you would have data highly fragmenting states, it would have to switch, and as explained above, that will hurt performance
Quote:
> This is why all negative input wouldn't improve, and (pos,neg,pos,neg,pos,neg....) input would be really worst case
 
but how you can influence the state switching? the data is as is, random or not, and it "controlls" the switching
I mean, you cannot reorder the data
 
 
2 hours later…
6:48 PM
hi I'm back
You can influence the state switching by refusing to switch. Think of it this way: the loopify stage is applicable to any input data at all (it is your original function, essentially). If the problem is "switching to the 'fastforward' stage too often", you could simply stay in the loopify stage for a minimum amount of time. One way to do this is to make the loopify stage unrolled for say 4,8 or 12 'frames'.
That would have two benefits: avoid state switching (which hinders instruction pipelining) and the benefits of loop unrolling<sup>1</sup>.
<sup>1</sup>: that requires a motivation as my earlier benchmarks showed that manual unrolling did not improve performance (at least on g++). Thing is, that was in the context of 1 homogenous loop. However, now with the modified algorithm, the compiler sees the extra loop end condition in loopify and might decide not to unroll anyway, so - back to square one with loop unrolling: this optimization _might make sense (of course looking at the assembly code would help decide without trying).
Whether all of this makes sense, depends on the actual data you feed into it.
 
 
5 hours later…
11:31 PM
Ok I'm off to bed. I didn't get around to updating the answer itself. Nevermind, I know you have the goods already. I came up with another idea to further enhance performance, I think. I haven't tested that, perhaps I'll describe it first tomorrow, so you'll have an exercise left over :)
Tomorrow is a working day for me so not much time. I'll keep an eye on the chat though
 

  last day (31 days later) »