Solving the 'if' statement problem



  • @Enterprise Architect said:

    Back to your SO answer: if we needed a dynamic mapping, something like this might make more sense. Let's assume we do need this, and let's take it a step further: suppose we want to support adding additional partitions between the existing partitions at runtime. How do we do that with your class?
     

    We can't, by design. My class is immutable (a highly desired condition in java, see Java Language Best Practices) and hence does not support additional valuies after initialization. If one needed that, one would have to declare the Mapper as an instance variable of a service class and re-initialize that variable with a new Mapper.

    @Enterprise Architect said:

    Would you design a user interface without considering what end users are actually trying to accomplish? Why design a programming interface without considering real-world applications?

    Of course not.  But as a Consultant, I might come up with a demo version of my suggested approach. If the Customer likes it, than that's the way we go. This is an opportunity I don't have in a SO situation. But the question title was "Get rid of ugly if statements", and that is exactly what I did.



  • @mostlymagic said:

    My class is immutable (a highly desired condition in java, see Java Language Best Practices) and hence does not support additional valuies after initialization.

    Right. Strings are immutable too, but they make it easy to make a new string from an old one:

    String string = "Hello";
    string = string + ", world";
    What's the equivalent with your class? How do I make a new instance that's just like the old one, but with a new rule added? If I can't, this is ill-suited to values that change at runtime, which is a really weird direction for an ultra-flexible object oriented solution to take.


  • @Enterprise Architect said:

    Strings are immutable too, but they make it easy to make a new string from an old one:

    String string = "Hello";
    string = string + ", world";

    What's the equivalent with your class?
     

    a) I guess you are aware that we don't have operator overloading in java. The special handling that Strings and primitives get is not an option to custom classes. Which is sometimes sad, but most of the times a good thing. Developers get what they expect, they don't have to search the code base for some hidden overloading to check it's semantics.

    b) Sure, I guess it would be possible to add a copy constructor that would either add or remove a mapping entry, but last time I checked, I was under fire for creating too much code, and now you want additional features? Which is it going to be?

    Also, due to syntax restrictions in java, the call syntax would have to be very awkward. Something like this:

    Mapper<Integer, Integer> newMapper = originalMapper.addKey(230).addValue(7)

    would unneccessarily create two new Instances (which is the way a functional language would do it, but java objects are heavier than their functional equivalents) or give up immutability. Also, it would not give me the option to insert the value at arbitrary positions (the key would be sorted to the correct position) without something like this

    originalMapper.addValue(int value, int offset)

    The key problem here is that there are no associative arrays in java. In another language I might have written something like this:

    Mapper mapper = Mapper.create([10 -> 1, 20 -> 2, 30 -> 3]) etc.

    And then the copy factory method would be something like

    newMapper = oldMapper.withAdditionalMappings([50 -> 4, 80 -> 5])

    But things like that are impossible in java.

    I'd say adding and removing values is not an option with this solution without turning it into a real monstrosity. Create a new instance instead.

    BTW, how are you going to create new mappings at runtime using the classic if/else solution you seem to favor?

    BTW (2) this is awful code

    @Enterprise Architect said:

    String string = "Hello"; string = string + ", world";

    It works, as a "convenience" for developers, but it internally creates lots of StringBuilder calls and it's hell to step through that with a debugger.

    Use

    newString = oldString.concat(", world")

    instead or if you are going to concatenate multiple elements, use a StringBuilder.



  • I realize the syntax has to be a bit kludgy in Java. Java programmers should be used to it by now.

    I also realize "modifying" an immutable object by making an updated copy wastes effort. Immutability is nice because you can guarantee your object will never change on you, but it comes with the penalty that you can't just edit it even when you know you can get away with it.

    My point is, you could have at least gained some useful flexibility by taking an object oriented approach. This might have made all the extra code worthwhile.

    Here, try this on:

    import java.util.*;
    

    public class Mapper<Key extends Comparable<Key>, Value> {
    private static class Entry<Key extends Comparable<Key>, Value>
    implements Comparable<Entry<Key, Value>> {
    private final Key thresholdValue;
    private final Value returnValue;

    	private Entry(final Key thresholdValue, final Value returnValue) {
    		this.thresholdValue = thresholdValue;
    		this.returnValue = returnValue;
    	}
    
    	public int compareTo(final Entry&lt;Key, Value&gt; o) {
    		return thresholdValue.compareTo(o.thresholdValue);
    	}
    }
    
    final private SortedSet&lt;Entry&lt;Key, Value&gt;&gt; entries;
    
    private Mapper(final SortedSet&lt;Entry&lt;Key, Value&gt;&gt; entries) {
    	this.entries = entries;
    }
    
    public Mapper() {
    	entries = new TreeSet&lt;Entry&lt;Key, Value&gt;&gt;();
    }
    
    public Mapper&lt;Key, Value&gt; newWithMapping(final Key thresholdValue,
    		final Value returnValue) {
    	final SortedSet&lt;Entry&lt;Key, Value&gt;&gt; newEntries =
    		new TreeSet&lt;Entry&lt;Key, Value&gt;&gt;(entries);
    	newEntries.add(new Entry&lt;Key, Value&gt;(thresholdValue, returnValue));
    	return new Mapper&lt;Key, Value&gt;(newEntries);
    }
    
    public Value map(final Key v) {
    	Value size = null;
    	for (final Entry&lt;Key, Value&gt; entry: entries) {
    		if (v.compareTo(entry.thresholdValue) &gt; 0)
    			size = entry.returnValue;
    	}
    	return size;
    }
    
    public Collection&lt;Value&gt; mapAll(final Collection&lt;? extends Key&gt; items) {
    	Collection&lt;Value&gt; result = new ArrayList&lt;Value&gt;(items.size());
    	for (final Key item: items) {
    		result.add(map(item));
    	}
    	return result;
    }
    
    public static class Builder&lt;Key extends Comparable&lt;Key&gt;&gt; {
    	final Key[ ] thresholdValues;
    	
    	private Builder(final Key[ ] thresholdValues) {
    		this.thresholdValues = thresholdValues;
    	}
    	
    	public &lt;Value&gt; Mapper&lt;Key, Value&gt; to(final Value... returnValues) {
    		if(returnValues.length != thresholdValues.length)
    			throw new IllegalArgumentException(
    					&quot;'from' and 'to' arrays must be equal length!&quot;);
    		SortedSet&lt;Entry&lt;Key, Value&gt;&gt; entries =
    			new TreeSet&lt;Entry&lt;Key, Value&gt;&gt;();
    		for (int i=0;i&lt;returnValues.length; ++i)
    			entries.add(new Entry&lt;Key, Value&gt;(thresholdValues[i],
    					returnValues[i]));
    		return new Mapper&lt;Key, Value&gt;(entries);
    	}
    }
    
    public static &lt;Key extends Comparable&lt;Key&gt;&gt; Builder&lt;Key&gt;
    mapValuesGreaterThan(final Key... thresholdValues) {
    	return new Builder&lt;Key&gt;(thresholdValues);
    }
    

    }

    Usage is easy enough. All of these are equivalent:
    Mapper<Integer, Integer> mapper = new Mapper<Integer, Integer>()
    .newWithMapping(10, 6)
    .newWithMapping(22, 5)
    .newWithMapping(51, 4)
    .newWithMapping(68, 3)
    .newWithMapping(117, 2)
    .newWithMapping(145, 1);

    Mapper<Integer, Integer> mapper = Mapper
    .mapValuesGreaterThan(10, 22, 51, 68, 117, 145)
    .to( 6, 5, 4, 3, 2, 1);

    Mapper<Integer, Integer> mapper = Mapper
    .mapValuesGreaterThan(145, 117, 68, 51, 22, 10)
    .to( 1, 2, 3, 4, 5, 6);

    Mapper<Integer, Integer> mapper = Mapper
    .mapValuesGreaterThan(145, 117, 51, 22, 10)
    .to( 1, 2, 4, 5, 6)
    .newWithMapping(68, 3);

    Advantages:

    • Mapping can be adapted at runtime. This is done by constructing a new object, so this is still immutable. This is a real win over raw if statements if you need this flexibility.
    • Entries can be given in any order. There were two working ways to order the if statements… why give up this flexibility?
    • Function names are a bit more descriptive. This could still use work in that area.

    If you're gonna go object oriented, go all in!

    Of course, if what you have is a set of static conditions, if statements are still the way to go.



  • @Enterprise Architect said:

    Here, try this on:
     

    Yup, definitely a nice solution. My approach was to use arrays internally to keep the memory footprint smaller (I know, Premature Optimization ...) , but using a Sorted Collection is nicer, I agree. Although I don't understand what you gain by using a SortedSet of Entry objects instead of using a SortedMap in the first place. And if you are using a SortedMap, you might as well use the advanced lookup functionality they provide because you are making the same mistake I was making (looping over the entire data structure to find the entry instead of partitioning the search, which SortedMap or rather NavigableMap supports natively using the lowerEntry() method.

    But still: a very elegant solution for a tech demo and if you had posted it in the first place you'd have gotten my upvote for sure, but then perhaps you'd also have been WTFed, who knows.



  •  @mostlymagic said:

    So: while I agree with 90% of Joel's pieces, I would take this one with a grain of salt. First of all: a lot of what he is complaining about is not Architect Speak, it's Marketing Speak (and I guess all Developers hate that). But, to stick with the Architect metaphor: you need both a good architect and good builders to build a house. If the Builders are bad, the walls will fall down. If the Architect is bad, no one will ever want to live there. Both are undesirable, especially from a business viewpoint.

    I think one important aspect of software development (and probably any other creative process) is being able to delegate tasks. Do the things you are good at and let others do what they are good at. Joel seems to think that anbody who doesn't understand pointers is a bad programmer. Sure, they'd probably be bad C / C++ programmers (because you probably need pointers to get things done in these languages, I wouldn't know, I haven't touched any C language in about 15 years). But they could still be great developers in Java, Scala, Haskell, Erlang, Groovy, JavaScript, Ruby, PERL and dozens of other languages, all of which are in production very successfully on thousands of sites. Yes, every developer must learn algorithms and theory of software engineering. But does every developer need to know what happens at machine level? No siree.

    Joel contradicts himself. In one blog he wrote that someone who can program well in C or C++ would easily be able to program well in any language. Later he writes that he needs rapid development and someone who has played with the right toys will be more useful than someone who is a great programmer in theory but hasn't had the experience of that particular toy.

     



  • @topspin said:

    @Cbuttius said:

    This is how I would approach it in C++:

    [stuff with] upper_bound.

    @Cbuttius said:
    Actually I think I should be using lower_bound because if it is equal to the boundary it goes into the lower section

    That's exactly what's wrong with the "generalized" overkill solutions. The if statement is FAR easier to get right and doesn't require thinking about the edge cases, especially when reading the code.

     

    Yes but leads to O(N) code at the end of the day instead of O(log N), and you can be sure that before long they will grow it and add in more numbers and nobody will fix,.The only issue I potentially have with my Java solution is whether or not tailSet() actually copies the portion of the tree it is returning to you because if so that is of course horribly inefficient. I was simply "converting" the solution I would use in C++ as best as I could find. That would use std::lower_bound which does no more than return you an iterator, and you can use it in a sorted array or vector which is less clunky than a std::set and very fast to calculate its distance from the end.

    In reality if you want the really most efficient solution then write a proper index, i.e. have an array of size 154 or whatever the top boundary is, test the boundary conditions first and if it is between then look up in the index. Constant-time lookup, although less flexible of course as the boundary values could run into the millions and it would be totally inefficient to have a table that size.

     



  • @Cbuttius said:

    Joel contradicts himself. In one blog he wrote that someone who can program well in C or C++ would easily be able to program well in any language. Later he writes that he needs rapid development and someone who has played with the right toys will be more useful than someone who is a great programmer in theory but hasn't had the experience of that particular toy.

     

    That's not a contradition.  If you want someone who can be productive now in a particular language/toolset/OS/API, then someone with existing experience with that "toy" and good skilltalent is better (== more suitable) than someone with experience with other toys and the same level of skilltalent.  If the second person works with your desired toy long enough, then he will be as productive with it as the first one, but that "long enough" could be longer than the deadline for a small project.



  • @Cbuttius said:

    The only issue I potentially have with my Java solution is whether or not tailSet() actually copies the portion of the tree it is returning to you because if so that is of course horribly inefficient
     

    No, tailSet() presents a live view of a sub sequence. Nothing is copied (at least in TreeSet, the reference implementation). TreeSet is backed by a map, and TreeSet.tailSet() returns a new TreeSet backed by a live sub view of the original map



  • @mostlymagic said:

    Although I don't understand what you gain by using a SortedSet of Entry objects instead of using a SortedMap in the first place. And if you are using a SortedMap, you might as well use the advanced lookup functionality they provide because you are making the same mistake I was making (looping over the entire data structure to find the entry instead of partitioning the search, which SortedMap or rather NavigableMap supports natively using the lowerEntry() method.


    Good call! Changing it to use NavigableMap even shrinks the Mapper class considerably:
    public class Mapper<Key extends Comparable<Key>, Value> {
    final private NavigableMap<Key, Value> entries;

    private Mapper(final NavigableMap&lt;Key, Value&gt; entries) {
    	this.entries = entries;
    }
    
    public Mapper() {
    	entries = new TreeMap&lt;Key, Value&gt;();
    }
    
    public Mapper&lt;Key, Value&gt; newWithMapping(final Key thresholdValue,
    		final Value returnValue) {
    	final NavigableMap&lt;Key, Value&gt; newEntries =
    		new TreeMap&lt;Key, Value&gt;(entries);
    	newEntries.put(thresholdValue, returnValue);
    	return new Mapper&lt;Key, Value&gt;(newEntries);
    }
    
    public Value map(final Key v) {
    	Map.Entry&lt;Key, Value&gt; ent = entries.lowerEntry(v);
    	return ent == null ? null : ent.getValue();
    }
    
    public Collection&lt;Value&gt; mapAll(final Collection&lt;? extends Key&gt; items) {
    	Collection&lt;Value&gt; result = new ArrayList&lt;Value&gt;(items.size());
    	for (final Key item: items) {
    		result.add(map(item));
    	}
    	return result;
    }
    
    public static class Builder&lt;Key extends Comparable&lt;Key&gt;&gt; {
    	final Key[ ] thresholdValues;
    	
    	private Builder(final Key[ ] thresholdValues) {
    		this.thresholdValues = thresholdValues;
    	}
    	
    	public &lt;Value&gt; Mapper&lt;Key, Value&gt; to(final Value... returnValues) {
    		if(returnValues.length != thresholdValues.length)
    			throw new IllegalArgumentException(
    					&quot;'from' and 'to' arrays must be equal length!&quot;);
    		NavigableMap&lt;Key, Value&gt; entries = new TreeMap&lt;Key, Value&gt;();
    		for (int i=0;i&lt;returnValues.length; ++i)
    			entries.put(thresholdValues[i], returnValues[i]);
    		return new Mapper&lt;Key, Value&gt;(entries);
    	}
    }
    
    public static &lt;Key extends Comparable&lt;Key&gt;&gt; Builder&lt;Key&gt;
    mapValuesGreaterThan(final Key... thresholdValues) {
    	return new Builder&lt;Key&gt;(thresholdValues);
    }
    

    }

    @mostlymagic said:

    But still: a very elegant solution for a tech demo and if you had posted it in the first place you'd have gotten my upvote for sure, but then perhaps you'd also have been WTFed, who knows.

    Thanks. I really, really didn't want to encourage anyone to replace a short set of if statements with this though. Now, if the OP had asked how to make his conditions configurable, I might have posted something like this, depending on the specific needs involved.

    I did like your Builder intermediate object though. It does make setting up an instance a lot less verbose at the cost of making Mapper not much more complex. Given that you're already on this path, that's a nice addition.



  • @Cbuttius said:

    @topspin said:

    That's exactly what's wrong with the "generalized" overkill solutions. The if statement is FAR easier to get right and doesn't require thinking about the edge cases, especially when reading the code.

     

    Yes but leads to O(N) code at the end of the day instead of O(log N), and you can be sure that before long they will grow it and add in more numbers and nobody will fix,.

    The problem with that is, for small N, O(log N) can be worse than O(N) if the O(log N) solution has a larger constant factor. Sure, if you have 2000 partitions and this is running 200,000 times a second, the difference could mean something, but for 6 entries? I've not benchmarked it, but I wouldn't be surprised to learn the if statements are faster. It might be fun to find out when the crossover happens: when O(log N) starts netting a real performance gain.

    I had fun one day proving to a co-worker that a hash lookup (O(1) average case) was actually slower than a red-black tree (O(log N)) for N < 500 or so (with short strings as keys).



  • @Enterprise Architect said:

    The problem with that is, for small N, O(log N) can be worse than O(N) if the O(log N) solution has a larger constant factor. Sure, if you have 2000 partitions and this is running 200,000 times a second, the difference could mean something, but for 6 entries? I've not benchmarked it, but I wouldn't be surprised to learn the if statements are faster. It might be fun to find out when the crossover happens: when O(log N) starts netting a real performance gain.
     

    Yup,  that's way the Arrays.sort() methods in java uses different sort methods depending on the Arrays size (see source here). They use 7 as the threshold to determine which algorithm to use.



  • @Enterprise Architect said:

    Thanks. I really, really didn't want to encourage anyone to replace a short set of if statements with this though. Now, if the OP had asked how to make his conditions configurable, I might have posted something like this, depending on the specific needs involved.

    I did like your Builder intermediate object though. It does make setting up an instance a lot less verbose at the cost of making Mapper not much more complex. Given that you're already on this path, that's a nice addition.

     

    OK, I think we are at a point were we understand each other farely well and I can now crawl back under the rock I came from. See you around.

    I'll be back

     



  • @mostlymagic said:

    @Enterprise Architect said:

    The problem with that is, for small N, O(log N) can be worse than O(N) if the O(log N) solution has a larger constant factor. Sure, if you have 2000 partitions and this is running 200,000 times a second, the difference could mean something, but for 6 entries? I've not benchmarked it, but I wouldn't be surprised to learn the if statements are faster. It might be fun to find out when the crossover happens: when O(log N) starts netting a real performance gain.
     

    Yup,  that's way the Arrays.sort() methods in java uses different sort methods depending on the Arrays size (see source here). They use 7 as the threshold to determine which algorithm to use.

    After skimming like 20 posts of this in my email inbox, I only have one question:

    What the fuck is wrong with you people?



  • Your algorithms may scale at O(lg N), but my log grows at O(2^N) plus a huuuuuuge constant.

     



  • @frits said:

    Your algorithms may scale at O(lg N), but my log grows at O(2^N) plus a huuuuuuge constant.

     

    It's not only premature optimization, it's premature optimization of code nobody needs for any project ever.

    Do you do this at work? Like you go into the office and instead of writing the subsystem you've been assigned, instead you debate some little pointless class you almost never use all day? What do you tell your boss when he asks what you're doing?

    Don't you have a little "this doesn't fucking matter!" meter in your head, and go off to play Xbox when it dings? Because honestly, playing Xbox is more useful to society than this conversation.



  • @blakeyrat said:

    Do you do this at work? Like you go into the office and instead of writing the subsystem you've been assigned, instead you debate some little pointless class you almost never use all day? What do you tell your boss when he asks what you're doing?

    Wait… we're supposed to write code that actually does something useful?
    @blakeyrat said:
    Don't you have a little "this doesn't fucking matter!" meter in your head, and go off to play Xbox when it dings? Because honestly, playing Xbox is more useful to society than this conversation.

    Since when was any aspect of TDWTF useful to society?



  • @blakeyrat said:

    @frits said:

    Your algorithms may scale at O(lg N), but my log grows at O(2^N) plus a huuuuuuge constant.

     

    It's not only premature optimization, it's premature optimization of code nobody needs for any project ever.

    Do you do this at work? Like you go into the office and instead of writing the subsystem you've been assigned, instead you debate some little pointless class you almost never use all day? What do you tell your boss when he asks what you're doing?

    Don't you have a little "this doesn't fucking matter!" meter in your head, and go off to play Xbox when it dings? Because honestly, playing Xbox is more useful to society than this conversation.

     

    Are you yanking my chain?  I pretty much am saying what you are.  In plain English:  I am calling this entire thread a bigger cock/algorithm contest.  Hence the "my LOG grows at O(2^N) plus a huuuuuuge constant" comment.

     



  • @Steve The Cynic said:

    @eBusiness said:

    I wonder why noone has yet come up with the arithmetic branchless solution:

    size=(size-6)*(v<=10)+6-(v>22)-(v>51)-(v>68)-(v>117)-(v>145);
    return size;


    Because it isn't branchless?

    The ?: operator somewhat hides an if() statement, because something in the mind refuses to acknowledge the existence of an if() inside an expression.

    The > and <= operators totally hide the if() statements.  Deep down inside the compiled code is an (if (condition) use 1 else use 0) subexpression.
    But that depends on the architechture, and the compiler. It does seem to be a bit tricky on the X86 architecture, but you could replace the missing GT and LT operators by something like:

    Pseudo-assembly:
    CMP var1, var2
    XOR SF, OF

    Would be a quite efficient method if retrieving individual flag bits was as easy as it could be. I can tell that there is a load of ways to implement XOR SF, OF, though it seems that they are all a bit complicated.



  • We are discussing possible ways to handle this kind of situation and we post on these sites to discuss, not to handle the situation in hand.

    By giving possible solutions we allow the programmer to apply one of them to best fit the situation at hand. Of course the most configurable situation would allow the boundaries to be changed at run-time without a re-compile (although it might require a restart). We were also discussing whether the output values (i.e. size here) is also liable to change or will it always be a contiguous sequence.

    It is likely to have runtime performance issues only if  it Is being called a lot of times, and we then have to consider the impact of whether more boundaries will be introduced thus a linear solution would start to get long. The constant-time lookup may well be the best solution if the upper boundary is never going to exceed a certain point and the boundaries will always be integral. (That doesn't mean the data will never exceed it, just the boundary).

     



  • See the X86 SET* instructions: you can extract individual flags. Also, GCC's compilation of this line (at least with -m32 -Os) is branchless.



  • @frits said:

    Are you yanking my chain?  I pretty much am saying what you are.  In plain English:  I am calling this entire thread a bigger cock/algorithm contest.  Hence the "my LOG grows at O(2^N) plus a huuuuuuge constant" comment.

    Sorry, you got me. I skimmed it. I thought you were just posting on the same thread, because jokes usually don't involve big-O notation.



  • @blakeyrat said:

    because jokes usually don't involve big-O notation.
    Mostly because of premature optimization.



  • @blakeyrat said:

    @frits said:
    Are you yanking my chain?  I pretty much am saying what you are.  In plain English:  I am calling this entire thread a bigger cock/algorithm contest.  Hence the "my LOG grows at O(2^N) plus a huuuuuuge constant" comment.
    Sorry, you got me. I skimmed it. I thought you were just posting on the same thread, because jokes usually don't involve big-O notation.

     

    Sorry, I was just trying to parody the "improvers".  I think they should post their solutions to stackoverflow.

     



  • @Enterprise Architect said:

    See the X86 SET* instructions: you can extract individual flags. Also, GCC's compilation of this line (at least with -m32 -Os) is branchless.
    Indeed..  However, don't lose sight of the fact that there are things in this world that are NOT x86.  (And technically speaking, the SETcc instructions extract individual conditions rather than individual flags, but that's purposelessly pedantic.)



  • Yeah, like x86_64 :-P

    Not that it matters. I still wouldn't be surprised to learn the branching's faster. That's a lot of senseless multiplication…



  • True, but a CPU pipeline is also rather long. Though between the optimization performed by the compiler and the CPU, I don't think it matters much in general.


  • BINNED

    @Enterprise Architect said:

    I still wouldn't be surprised to learn the branching's faster. That's a lot of senseless multiplication…

    Well, it's definitely faster than those "fast O(log n)" solutions.
    I guess the multiplications are slower than the possible branch mispredictions, but one would have to profile that to know for sure.

     

     

    @mostlymagic said:

    My class is immutable (a highly desired condition in java, see Java Language Best Practices)

    I haven't done any Java in a while but the same page says "2.11 Reuse Objects Instead of Creating New Ones If Possible", which contradicts the immutable advice IMO. It even goes as far as "Object creation is an expensive operation in Java", but a major advantage of the heap compacting garbage collector is that memory allocation is very cheap.



  • @Steve The Cynic said:

    @Enterprise Architect said:

    See the X86 SET* instructions: you can extract individual flags. Also, GCC's compilation of this line (at least with -m32 -Os) is branchless.
    Indeed..  However, don't lose sight of the fact that there are things in this world that are NOT x86.  (And technically speaking, the SETcc instructions extract individual conditions rather than individual flags, but that's purposelessly pedantic.)

    Ahh, yes, deep in the pile of 386 instructions the SET commands are buried, no problem then, any sane compiler on the 386+ platform will have implemented inequalities in the operator fashion where appropriate. As for non-x86 platforms, I think you'll find similar instruction on most of them, so it shouldn't change the principal arguments.

    Of course I wrote the branchless solution with the sole premise that it should be branchless. However, you shouldn't underestimate the performance advantage of avoiding branches. Multiplication and division is expensive operations on very old hardware, but dedicated units for these operations are old news, today all 32 bit arithmetic functions are dirt cheap, multiple per clock cycle can be performed. A branch prediction miss cost a lot more than a few arithmetic or low level operator functions.

    I'd guess that the fastest method for the problem type is to use a few branches (set up in a neatly balanced tree structure rather than being daisy chained, of course) to cut the number of possible outcomes exponentially, and then use a branchless approach instead of the last 1 or 2 branches.



  • Why guess? Test! You're right though: I measure the branchless to be noticeably faster: for 100,000,000 iterations and rand() % 179 as input, I measure 0.856s vs. 1.928s for the if statements (test harness overhead of 1.221s was subtracted from both results).

    This is C though, so it's irrelevant to Java, and it's even more irrelevant if your hardware isn't similar to mine.



  • @Enterprise Architect said:

    Why guess? Test! You're right though: I measure the branchless to be noticeably faster: for 100,000,000 iterations and rand() % 179 as input, I measure 0.856s vs. 1.928s for the if statements (test harness overhead of 1.221s was subtracted from both results).

    This is C though, so it's irrelevant to Java, and it's even more irrelevant if your hardware isn't similar to mine.

    Why would I waste my time doing such a menial task when you do it for me? ;-)

    Your test is not irrelevant to Java or different hardware, while you will of course not get the exact same result, the general conclusion is the same across almost all modern computers and compilers: Despite the incomplexity, branching is expensive. A multiply and add instruction may however cost no more than a bitshift operation.



  • @eBusiness said:

    Multiplication and division is expensive operations on very old hardware, but dedicated units for these operations are old news, today all 32 bit arithmetic functions are dirt cheap, multiple per clock cycle can be performed.
     

    I keep reading that, but I have not experienced it for division. Multiplication is fast since, I don't know, ten years maybe? But I've not yet had access to a box where division was fast, still takes multiple cycles in the uncharted backwater of the galaxy I live in.


  • I guess I better stick my head into some C or Assembly and come up with some numbers. For now I'll just spill the fact that you are almost never doing arithmetic on it's own, real code is always stuffed with reads and writes to memory, which tend to waste some time, even when the memory block is in the processor cache.



  •  Well, it may just be our shitty hardware. But when you're doing number-theoretic calculations, you do a lot of arithmetic on its own, preferably in tight loops. So I'm in the 'almost never' fragment (yes, it's rare, but it happens).



  • @eBusiness said:

    I wonder why noone has yet come up with the arithmetic branchless solution:

    size=(size-6)*(v<=10)+6-(v>22)-(v>51)-(v>68)-(v>117)-(v>145);
    return size;

     

     Variation of the theme:

        int foo(int i) {
            assert i > Integer.MIN_VALUE + 145;
            return 7 + ((10 - i) >> 31) + ((22 - i) >> 31) + ((51 - i) >> 31)
                    + ((68 - i) >> 31) + ((117 - i) >> 31) + ((145 - i) >> 31);
        }

    New objective: Rewrite the Mapper class from above to emit branchless byte code! Only solutions longer than 24k lines will be accepted!

    Filed under: If the only tool you have is a book about bit twiddling ...



  • @blakeyrat said:

    I think they're more interested in showing people how smart they are. "Oh, your interviewees can't do it? Look how easy it is for me, a super-genius with a huge dick!!!"

     

    How did you know I was a Super-Genius?



  • @Medezark said:

    How did you know I was a Super-Genius?

    Wait. You can solve FizzBuzz?

    Pics or it didn't happen!



  • @blakeyrat said:

    FizzBuzz
    Clearly this needs some more enterprisey solutions. Today, we'll add some enterprise with C++:@the depths of Hell said:
    #include <algorithm>
    #include <iostream>
    using std::for_each;

    template<typename T>
    class number_seq {
    private:
    const T _begin, _end;
    public:
    class const_iterator {
    private:
    T value;
    public:
    const_iterator() {}
    const_iterator(const T&x) : value(x) {}
    const_iterator &operator++() {
    ++value;
    return *this;
    }
    const_iterator operator++(int) {
    const_iterator result(this);
    ++value;
    return result;
    }
    const T& operator
    () const {
    return value;
    }
    const T& operator->() const {
    return value;
    }
    bool operator==(const const_iterator &x) const {
    return value == x.value;
    }
    bool operator!=(const const_iterator &x) const {
    return value != x.value;
    }
    };
    number_seq(T begin, T end) : _begin(begin), _end(end) {}
    const_iterator begin() {
    return const_iterator(_begin);
    }
    const_iterator end() {
    return const_iterator(_end+1);
    }
    };

    template <typename T, T modVal>
    class is_multiple {
    public:
    bool operator()(const T& x) const {
    return (x % modVal) == 0;
    }
    };

    template <typename T, typename Fizz, typename Buzz>
    class fizz_buzz {
    private:
    Fizz fizz;
    Buzz buzz;
    public:
    void operator()(const T& x) const {
    if(fizz(x))
    std::cout << "Fizz";
    if(buzz(x))
    std::cout << "Buzz";
    if(!(fizz(x) | buzz(x)))
    std::cout << x;
    std::cout << std::endl;
    }
    };

    int main(int argc, char *argv[ ]) {
    number_seq<int> numbers(1, 100);
    fizz_buzz<int, is_multiple<int, 3>, is_multiple<int, 5> > fizzbuzz;
    for_each(numbers.begin(), numbers.end(), fizzbuzz);
    return 0;
    }


Log in to reply