Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am a Java developer building a web app that I will be deploying "in the cloud" (I hate that expression) in a few months. I'm trying to develop a function that will let me spawn and kill the right amount of "computing horsepower" (virtual machines) depending on the current load of the system (by "load" I mean traffic, # of users, etc.).

I have developed such a function, but because it's been so long since I cracked open any of my college mmathbooks, there's one component of it that I'm struggling with that could/should be re-written as it is a piecewise function.

Basically, I have an "outer"/main function c that maps a real (the load) to an integer (# of virtual machines I should have running to support the load):

c : L in the domain of reals --> z in the domain of integers
c(L) = A * t(L)

Where c(L) is the function that my Java code will call, L is a measure of the current load on the system (of type double since load could be 5.0 or 34.2094, etc.), A is a fairly-complicated function that doesn't concern this question (so I omitted it), and t(L) is the piecewise function I need help re-writing:

t(L) = {    0 : if L < 1
       {    L+1 : if L is an integer // 5.0 == 5
       {    ceil(L) : if L is not an integer // 5.5

I understand that the first and third piecewise rules sort of contradict each other, but the first one (0 : if L <1) trumps/overrides the last one (ceil(L) : if L not integer).

So, if L is less than 1, I need t(L) to always return 0. Otherwise, if its an integer, I need it to return L+1, or ceil(L) for any other reals.

So, some examples:

t(0.5) = 0
t(1) = 2 // 1 + 1 -> 2
t(1.5) = 2 // ceil(1.5) -> 2
t(2) = 3
t(57.39854) = 58

Note: L will always be non-negative (0+).

For the life of me I can't figure out how to re-write t(L) in such a way as to be "in-line" or normal (not containing if-else piecewise rules). Thanks for any and all help here!

share|improve this question
2  
The two last cases are just floor(L+1), aren't they? –  Henning Makholm Jul 6 '12 at 12:34
2  
I don't understand why a piecewise function is a problem. –  Rahul Jul 6 '12 at 12:37
2  
@zharvey: Do you have actual benchmarks telling you that a single conditional jump is going to be a performance bottleneck here? Most attempts to replace your expression with something that looks syntactically uniform will be much more expensive to compute. If you're talking massive SIMD (e.g., running on a GPU), then any such system with even a halfway-decent compiler should be able to handle local if-elses using selective disabling of data paths per instruction based on local condition flags. –  Henning Makholm Jul 6 '12 at 12:46
4  
Sounds like a programming problem to me, maybe more suitable for another site. –  Gerry Myerson Jul 6 '12 at 12:56
6  
@Adam: Now I don't understand why you are speaking as if this is your question. Are you the same person as zharvey? If so, are you congratulating yourself in this comment? I'm only asking so I know how to address (the one or two of) you in future comments. –  Rahul Jul 7 '12 at 1:39
show 11 more comments

2 Answers

Would

L < 1 ? 0 : (int)L+1

be streamlined enough for you? I don't think there's any simpler way to write your function in Java.

Yes, this expression uses the ternary conditional operator ?:, which is essentially equivalent to an if–else clause except that it switches between expressions instead of blocks. Depending on how smart your compiler is, the resulting assembly code may or may not end up involving an actual conditional jump.

Still, I very much doubt that this expression will be the performance bottleneck in your application. In fact, if it's really going to be part of a load balancer, I doubt it will even make a measurable difference at all — if the calculation is done, say, once per second, a few nanoseconds lost to a branch misprediction will be like a drop in the ocean. Unless this code really makes up a major part of the inner work loop of your program, micro-optimizing it like this probably violates Knuth's rule on premature optimization:

"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."

share|improve this answer
1  
Well, if one really wants to avoid conditional jumps one could try int t = (int)(L+1); t &= ~(t-2)>>31; -- though that is pretty horrible and definitely shouldn't be used without benchmarking to justify the lost readability. –  Henning Makholm Jul 6 '12 at 13:11
    
Or int t = (int)L+1; t *= 2-(int)((t+1.0)/t); If $t=1$, then $(t+1)/t = 2$, therefore $t$ will be multiplied by $0$ (note that both $1.0$ and $2.0$ can be represented exactly, so no rounding errors should occur in this case). In the other hand, for $t>1$, we have $1<(t+1)/t<2$ and therefore conversion to int gives $1$ (and we are far away from $2$, so rounding errors should again not create problems here). However if removing the conditional jump is for speed reasons, this is probably a bad idea. –  celtschk Jul 6 '12 at 13:28
1  
I hope you're joking: saving a few microseconds when computing the number of tasks to be launched is absolutely negligible compared to actually launching a virtual machine instance... The only case where performance might matter is $L<1$, since it could be executed many times without actually launching anything. But even that seems completely negligible as compared to e.g. the cost of actually measuring the load. –  Generic Human Jul 6 '12 at 14:27
1  
You have all mis-read my question. This function will help calculate how many virtual machines are running in our production environment; this is how all cloud-based pricing works: the more VMs ("horsepower") you're running, the more they bill you. –  Adam Tannon Jul 6 '12 at 17:13
2  
@zharvey: But what is the problem with the function being piecewise? –  celtschk Jul 9 '12 at 10:50
show 4 more comments

I figured it out:

t(L) = floor((3L+1)/(2L+2)) + floor(L)

Try it out:

t(0.6) = 0
t(1) = 2
t(1.6) = 2
t(5.8) = 6
t(50) = 51

Doesn't work when L < 0, but like I said that use case will never occur because L will always be non-negative. Achieves exactly what I asked as my original question.

share|improve this answer
1  
What have you gained doing this? Now you have two multiplications, one division, several additions and two calls to floor(). –  mrf Jul 6 '12 at 15:49
1  
Please see my comment to @Gerneric Human. Forget about the nastiness of the function (as you say, multiple floor calls, etc.). This function gives me the precise mapping of inputs to output that I was looking for in my original question; hence it is the answer. Whereas everybody jumped on the concurrency/optimization bandwagon (which was not in fact the problem mentioned in my original question), I was looking for a way to define t(L) without having to use piecewise "rules" (or whatever you math guys call them). The question was as simple as that. –  Adam Tannon Jul 6 '12 at 17:15
    
Well done, sir. This is a classic example of what happens when "StackExchangers love answering the wrong question" meets the "mob mentality". –  Adam Tannon Jul 6 '12 at 17:18
    
Well, congratulations for finding an answer you like. (Ps. If this is the kind of expression you're looking for, then t(L) = floor(2L/(L+1)) + floor(L) would arguably be even simpler.) –  Ilmari Karonen Jul 6 '12 at 18:42
    
Thanks @IlmariKaronen - and I bet there are many variants of the first floor's arguments that would achieve the same thing. This is what I was asking though, and its not about "finding an answer that I like", per se, it's about finding an answer to the actual question and not getting sidetracked with a different problem altogether! –  Adam Tannon Jul 6 '12 at 23:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.