×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

IBM Releases Open Source Machine Learning Compiler

timothy posted more than 4 years ago | from the what-you-meant-to-say-is dept.

Programming 146

sheepweevil writes "IBM just released Milepost GCC, 'the world's first open source machine learning compiler.' The compiler analyses the software and determines which code optimizations will be most effective during compilation using machine learning techniques. Experiments carried out with the compiler achieved an average 18% performance improvement. The compiler is expected to significantly reduce time-to-market of new software, because lengthy manual optimization can now be carried out by the compiler. A new code tuning website has been launched to coincide with the compiler release. The website features collaborative performance tuning and sharing of interesting optimization cases."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

146 comments

"Learning" (0)

quantum bit (225091) | more than 4 years ago | (#28568669)

Joshua? Is that you?

Re:"Learning" (0)

ocularDeathRay (760450) | more than 4 years ago | (#28568773)

Nope... its Mycroft Holmes

They kept hooking hardware into him--decision-action boxes to let him boss other computers, bank on bank of additional memories, more banks of associational neural nets, another tubful of twelve-digit random numbers, a greatly augmented temporary memory. Human brain has around ten-to-the-tenth neurons. By third year Mike had better than one and a half times that number of neuristors. And woke up.

Some logics get nervous breakdowns. Overloaded phone system behaves like frightened child. Mike did not have upsets, acquired sense of humor instead. Low one. If he were a man, you wouldn't dare stoop over.

TANSTAAFL bitches.

Automation... (2, Insightful)

juanergie (909157) | more than 4 years ago | (#28568681)

... can create stupid humans. Let's embrace technology but beware of falling into ignorance.

Re:Automation... (0)

Anonymous Coward | more than 4 years ago | (#28568711)

I fail to see how automation leads to lower IQ scores. Care to elaborate? How does stepping up the pace, and eliminating tedious, mundane jobs, lead to a lesser society? I call FUD.

Re:Automation... (2, Informative)

TinBromide (921574) | more than 4 years ago | (#28568723)

I fail to see how automation leads to lower IQ scores. Care to elaborate? How does stepping up the pace, and eliminating tedious, mundane jobs, lead to a lesser society? I call FUD.

wooooosh.
See idiocracy. Go out and watch it. I'll wait








Saw it? Good, now you should get the joke.

Re:Automation... (2, Informative)

Fluffeh (1273756) | more than 4 years ago | (#28569061)

I would argue. Either you get it without needing to watch the movie simply by being surrounded by people who in their day to day existence simply follow instructions blindly "because they have to" or you won't get it - whether you watch the movie or not.

As for the GP, I believe he is mixing two things incorrectly:

fail to see how automation leads to lower IQ scores
and
lead to a lesser society

Lower IQ scores don't immediately mean a lesser society, but if you take the thinking out of a process and let a process/machine/program do all the thinking, your mind will inevitably get lazy and your work will suffer over time

Re:Automation... (0)

Anonymous Coward | more than 4 years ago | (#28569103)

That's what the professors want you to believe! There is absolutely nothing in our history that suggests that automation is harming our society, creating a lazy, good for nothing, sub-standard, citizen. Again, I call FUD. You're suggesting that calculators have harmed society. On the contrary, they and computers have excelled society into a new era of information technology. You can call me lazy for using a calculator, but I guarantee you my work isn't suffering from its use.

Re:Automation... (3, Insightful)

piojo (995934) | more than 4 years ago | (#28569167)

if you take the thinking out of a process and let a process/machine/program do all the thinking, your mind will inevitably get lazy and your work will suffer over time

I think that it could very well free your mind to think about better things. Build systems are a good example. If I had to manually compile each translation unit, I couldn't spend as much time thinking about the code.

Re:Automation... (2, Insightful)

michelcolman (1208008) | more than 4 years ago | (#28569993)

Most programmers stopped "thinking about the code" long ago and just slap together a bunch of libraries. That's why my DVD/HD player takes about 30 seconds loading operating systems (I hope that last 's' is an exaggeration, but I fear it may even be correct) before it will even eject a disc. As for the supposedly huge performance improvement of 18% (that's all?!), I have regularly hand-optimised code that ran more than twice as fast.

Re:Automation... (2, Insightful)

h4rm0ny (722443) | more than 4 years ago | (#28569337)


Abstraction is one of the foundations of higher thinking. There is something to be said for being able to do lower-level tasks, but you don't concern yourself with the internals of them when you want to treat them as discrete objects. Nobody thinks about the construction of an AND gate when they're designing something that uses AND gates. Nobody thinks about the internal workings of a method or function when they simply want to call it. In every area, the process is the same: You first learn the basic components, and then you assemble them into a composite of those components (whether a function, a muscial chord, a template in an MVC or whatever), and operate on a higher level.

It's been too many years since I've really worked with compilers directly, but to me this looks impressive. Can someone who is more up to date with the field tell me if this is an appropriate moment to go: "Woah!" Because I feel like it might be.

Re:Automation... (2, Insightful)

aaribaud (585182) | more than 4 years ago | (#28570013)

Joke aside, as for any rather absolute statement, there is only a part of truth both in the statement and in its opposite. Granted, automation does not necessarily lead to a lesser [level of intelligence in] society. However, not everything that automation can do must necessarily be done by automated means. For instance, calculators have automated calculus. I for one, welcome our key-laden overlords from arctangent, because I rarely have to compute arctangent and find it handy to have a calculator to do it for me. However, calculators can also do simple arithmetic like additions and multiplications ; and this can (and does, in the experience I can gather from my immediate vicinity) lead to a lessening of people's capability at doing additions and multiplications -- operations which are much more frequent than arctangents.

Re:Automation... (2, Interesting)

tkinnun0 (756022) | more than 4 years ago | (#28570671)

See idiocracy. Go out and watch it. I'll wait

The main tenets in Idiocracy were that IQ is hereditary and those with less IQ spend more time procreating. Automation was merely allowing their society to function, barely. IOW, I don't see your point. Can you elaborate, please?

Re:Automation... (0)

Anonymous Coward | more than 4 years ago | (#28570289)

... can create stupid humans. Let's embrace technology but beware of falling into ignorance.

Impoverished people have a higher IQ than wealthy people. Use it or lose it.

Oh really? (5, Insightful)

zmotula (663798) | more than 4 years ago | (#28568689)

The compiler is expected to significantly reduce time-to-market of new software, because lengthy manual optimization can now be carried out by the compiler.

Oh, so new software takes too long to build because of lengthy manual optimization? That's news indeed. Even if it did, will the compiler find a better polygon intersection algorithm for me? Will it write a spatial hash? Will it find places when I am calculating something in a tight loop and move the code somewhere higher?

Re:Oh really? (5, Interesting)

lee1026 (876806) | more than 4 years ago | (#28568715)

The last one is actually quite possible, and indeed is a huge area of compiler research.

Re:Oh really? (1)

Rosco P. Coltrane (209368) | more than 4 years ago | (#28569035)

will the compiler find a better polygon intersection algorithm for me? Will it write a spatial hash? Will it find places when I am calculating something in a tight loop and move the code somewhere higher?

The real question in everybody's mind is: will it blend? [willitblend.com]

Re:Oh really? (3, Funny)

Thanshin (1188877) | more than 4 years ago | (#28569215)

Oh, so new software takes too long to build because of lengthy manual optimization?

It depends on your definition of optimization.

In my current project we have about twenty guys "performing lengthy manual optimizations". It sounds quite better than having twenty guys "correcting the absolute crap that wouldn't even compile".

Re:Oh really? (2, Insightful)

Fullers (1590483) | more than 4 years ago | (#28569217)

Highly optimized software does take a long time to build because of manual optimization. Plus, if anything changes, that optimization might need to be done again. And yes, a good compiler will move that loop for you.

Re:Oh really? (0)

Anonymous Coward | more than 4 years ago | (#28569231)

Oh wow, you're so *great*. You know all those amazing words! I'm impressed to say at least.

Re:Oh really? (1)

TheRaven64 (641858) | more than 4 years ago | (#28569499)

Will it find places when I am calculating something in a tight loop and move the code somewhere higher?

Look up loop-invariant code motion. This has been supported in shipping compilers for a while.

Re:Oh really? (5, Informative)

jcupitt65 (68879) | more than 4 years ago | (#28569871)

Read the article, that's not what this does. This is a project to automatically generate optimising compilers for custom architectures. The summary is a little unclear :-(

It reduces time to market because you don't have to spend ages making an optimising compiler for your custom chip.

Re:Oh really? (2, Insightful)

John Hasler (414242) | more than 4 years ago | (#28570365)

Thanks. That is very, very different from what the summary says.

Re:Oh really? (3, Interesting)

DiegoBravo (324012) | more than 4 years ago | (#28570541)

That kind of confusing summaries are too frequent that sometimes I go to RTFA!

Seriously, the summaries should be subject to moderation too (I don't know if the firehose thing lets do that.)

There's this thing called algorithm recognition (1)

jonaskoelker (922170) | more than 4 years ago | (#28569883)

That's news indeed. Even if it did, will the compiler find a better polygon intersection algorithm for me? Will it write a spatial hash?

I TA'ed a course called Contract-based Programming (which was about Hoare triples and JML, a java extension which does checking of pre-/postconditions and invariants).

I noted that the lecturer had a book on his shelves titled "Algorithm recognition". I speculate that it might talk, for instance, about how to recognize bubble sort and replace it with quicksort. Or how sorted(list)[0] might be replaced by min(list), or how sorted(list)[4] might be replaced by quickselect(list, 4).

I don't know what state of the art is, though, but presumably future compilers might find a better polygon intersection algorithm for you. Or make better algorithm choices across abstraction boundaries. I would love to be able to think about "the smallest four elements" as take 4 (sorted list) and have the compiler make it run in O(n) time rather than O(n log n).

Re:Oh really? (1)

martas (1439879) | more than 4 years ago | (#28569963)

eventually, it'll probably re-write all of the code to do everything better, and without mistakes. but that's in about 100 years or so (probably more). for now, be happy with what you've got.

Re:Oh really? (1)

ShakaUVM (157947) | more than 4 years ago | (#28570099)

>>Oh, so new software takes too long to build because of lengthy manual optimization?

I indeed spend 18% of my coding time typing "gcc -O3".

Re:Oh really? (2, Informative)

kwikrick (755625) | more than 4 years ago | (#28570259)

No, this 'learning' compiler only learns how to optimally translate C++ statements to machine level operations. It cannot choose high level algorithms for you. And the reason that such a learning compiler is useful is not to help lazy application programmers, but because developing new, optimised compilers for the many different processors and platforms out there (think computers, mobile phones, embedded systems, etc) is time consuming.

Re:Oh really? (2, Funny)

maxwell demon (590494) | more than 4 years ago | (#28570585)

Oh, so new software takes too long to build because of lengthy manual optimization?

Yes. That's why most manuals are not very optimized. So the next time you think a manual is close to useless, don't complain. It's in order to save you time in the building process.

Less time? How about same time, better product? (3, Insightful)

TinBromide (921574) | more than 4 years ago | (#28568703)

The compiler is expected to significantly reduce time-to-market of new software, because lengthy manual optimization can now be carried out by the compiler.

How about this: The coders take the time they would have used to "optimize" and instead better document, test, and debug the code. Instead of same quality, less money, make it better quality, same money? You know that the developer isn't going to charge less money for a new product because it took them less time to get it out the door.

Re:Less time? How about same time, better product? (0)

Anonymous Coward | more than 4 years ago | (#28568955)

How about this: The coders take...

How about this: the coder's employer computes the time saved through automation and pockets the difference and/or lowers his bid.

How about this: the coder's employer hires a less talented/experienced/educated coder to replace his high cost coder and pockets the difference and/or lowers his bid.

Reality sucks.

Re:Less time? How about same time, better product? (1)

Thanshin (1188877) | more than 4 years ago | (#28569233)

Instead of same quality, less money, make it better quality, same money?

Yes, that always works.

I'm asking my client right now whether he wants a quality product in february or a barely working one in october. Let's see what happens.

Re:Less time? How about same time, better product? (1)

Esc7 (996317) | more than 4 years ago | (#28569359)

From my experience I can already tell you:

"Good enough product in November (early November!)"

Re:Less time? How about same time, better product? (1)

Lehk228 (705449) | more than 4 years ago | (#28569747)

bullshit. he's going to want it by august and it had better work!!!!11111eleventy!

Re:Less time? How about same time, better product? (1)

maxwell demon (590494) | more than 4 years ago | (#28570609)

If you ask hin in december, he certainly will opt for the quality product in february. :-)

Re:Less time? How about same time, better product? (1)

rawler (1005089) | more than 4 years ago | (#28569311)

That's what I'm afraid of. The big performance wins have never been in the final optimization-phase, but in doing a design aimed for performance, utilizing better algorithms to reduce resources spent.

Good thing programmers are now encouraged to think even less about that. "Oh, the compiler will probably optimize that away, and it's more readable like this."

Dumb Summary (5, Insightful)

QuantumG (50515) | more than 4 years ago | (#28568705)

automatically learn how to best optimise programs for re-configurable heterogeneous embedded processors

That's kinda important to mention no?

Re:Dumb Summary (3, Insightful)

mozzis (231162) | more than 4 years ago | (#28568819)

Absolutely. This is not for the normal processors we all know and love, nor is it any good for javascript or python etc. Compilers for C++, C#, java etc. on normal CPUs all have pretty ferocious optimizers already. Not that an attentive human programmer can't make much more of a difference, usually.

Re:Dumb Summary (1)

Thanshin (1188877) | more than 4 years ago | (#28569239)

automatically learn how to best optimise programs for re-configurable heterogeneous embedded processors

That's kinda important to mention no?

Well, it could be optimizing for unconfigurable homogeneous strawberry pudings.

It'd be quite more impressive, from a culinary standpoint.

Re:Dumb Summary (1)

Fullers (1590483) | more than 4 years ago | (#28569247)

Developing a good optimizing compiler quickly is very important when the hardware can change very easily, which is why it works well for reconfigurable processors. However, the results are impressive even on static architectures like x86 and PPC.

Few Questions for any programmers (2, Interesting)

contr0l (1590249) | more than 4 years ago | (#28568707)

I'm not a programmer at all, but have dabbled in a few different languages, as I find programming very interesting. (Got pretty good at mirc scripting when I was younger, which lead to visual basic, C++, and now C# dballing that nvr leads to anything). This said, I have a basic knowledge of programming in general. My question is, What things can a compiler do to your code to 'optimize' it for you? I would think majority of any good optimizations might require rethinking whole methods of doing things and/or recoding chunks of code. If the compiler tries to do this, wouldn't it likely screw your code up? Or how would it know 'what' your really trying to do? Outside of removing comments, can someone please explain other Basic optimization methods, (I say basic, like removing comments - You know that cant screw anything up), that a compiler can do on your code that wont screw it up? Thanks in advance.

Re:Few Questions for any programmers (5, Informative)

EvanED (569694) | more than 4 years ago | (#28568755)

What things can a compiler do to your code to 'optimize' it for you?

Check out the Wikipedia article [wikipedia.org] on optimization for some examples.

In brief, some of the more common ones are things like substituting known values for expressions (e.g. x = 3; y = x + 2; can be changed to x = 3; y = 5;), moving code that doesn't do anything when run repeatedly outside a loop, and architecture-specific optimizations like code scheduling and register allocation. (E.g. with no -O parameters, or -O0, for something like "y = x; z = x;" GCC will generate code that loads "x" from memory twice, once for each statement. With optimization, it will load it once and store it in a register for both instructions.)

If the compiler tries to do this, wouldn't it likely screw your code up?

There are cases where optimizations will screw something up. One example is as follows. It's considered good security practice to zero out memory that held sensitive information (e.g. passwords or cryptographic keys) to limit the lifetime of that data. So you might see something like "password = input(); check(password); zero_memory(password); delete password;". But the compiler might see that zero_memory writes into password, but those values are never read. Why write something if you never need it? So it would remove the zero_memory call as it's useless code that can't affect anything. So it removes it. And your program no longer clears the sensitive memory.

This was actually a bug in a couple crypto libraries for a while.

Re:Few Questions for any programmers (1)

contr0l (1590249) | more than 4 years ago | (#28568785)

I see, thanks for the detailed explanation, I hadn't thought of those. I like the first example, and the fact that the compiler can recognize your code and make that replacement confidently. Thats just cool.

Re:Few Questions for any programmers (1, Informative)

Anonymous Coward | more than 4 years ago | (#28569077)

There are cases where optimizations will screw something up. One example is as follows. It's considered good security practice to zero out memory that held sensitive information (e.g. passwords or cryptographic keys) to limit the lifetime of that data. So you might see something like "password = input(); check(password); zero_memory(password); delete password;". But the compiler might see that zero_memory writes into password, but those values are never read. Why write something if you never need it? So it would remove the zero_memory call as it's useless code that can't affect anything. So it removes it. And your program no longer clears the sensitive memory.

And it was the crypto library's fault, not the compiler's fault. Most languages worthy of doing crypto programming in have a facility to say ~"don't optimize this". An example: in C, the keyword "volatile" instructs the compiler that the field may be changed at any time, and thus all reads/writes must take place and must do so atomically [unfortunately, the C spec doesn't specify "in order" for volatile fields, but I digress].

Re:Few Questions for any programmers (1, Informative)

Anonymous Coward | more than 4 years ago | (#28569181)

The C spec doesn't require atomicity of volatiles, but it does require in order. So you've got it the wrong way round!

Re:Few Questions for any programmers (1)

EvanED (569694) | more than 4 years ago | (#28569207)

This is sort of a nit and not really germane to the current discussion about optimization, but...

An example: in C, the keyword "volatile" instructs the compiler that the field may be changed at any time, thus all reads/writes must take place and must do so atomically

"Atomically" isn't the right word for what "volatile" means. Basically, "volitile" specifies that reads should always come from memory, and writes should always go to memory. (This is as opposed to a register.) So for instance, if you had a loop where "x" was unchanged by the loop but you wanted to force it to be reloaded each time (because it might be changed by another thread for instance) you can declare "x" as "volatile int x" or whatever.

I think it is the case that accesses to volatile variables can't be reordered too.

There isn't really any guarantee of atomicity though; "x++" might not actually increment x (or might cause lost updates), and I suspect that a conforming implementation might be able to update, say, both words of a two-word integer independently on an operation (even though that could lead to races in multithreaded code and stuff like that).

Re:Few Questions for any programmers (0)

Anonymous Coward | more than 4 years ago | (#28570051)

"Atomically" in the sense of C means that either the update happens, or it doesn't: the machine is not left in a "hanging" state where half an update is applied to the variable. All writes and reads are applied. And yes, volatile reads and writes can be reordered (think of two threads attempting to write to a volatile variable; the compiler has no ability to say which write comes first, it is entirely runtime and machine dependent. They can even be reordered by the processor itself in many cases. Intel has gobs of information on the "correct" and best-performance yielding sequences of updates to volatile data/addresses for their architectures, e.g., but even the most naive of implementations can usually get pretty solid performance numbers).

This is entirely different from higher-level languages (C#/Java/etc) which use "volatile"/atomically in terms of machine synchronization, for which C is entirely oblivious to (in all cases, it is provided as a library or extension to the C specification which is entirely dependent on syscalls or atomic update routines). Volatile gives no threading guarantees once so ever in C, differently from the threading-aware languages mentioned above.

Re:Few Questions for any programmers (1)

michelcolman (1208008) | more than 4 years ago | (#28570023)

Another, more common problem in optimization is floating point math. For example, "T = S+Y; C = (T - S) - Y;" may be "optimized" to "T = S+Y; C = 0;" while the whole point of the calculation was that C contained the rounding error!

Re:Few Questions for any programmers (5, Insightful)

walshy007 (906710) | more than 4 years ago | (#28568763)

it optimizes the translation of to assembly opcodes. When you code the stuff you type is not in the binary that's compiled/assembled/linked.

I highly recommend you add a tiny amount of assembly programming dabbling to that list, and you will gain better understanding of how compiler optimization is not a simple affair. There are many ways to do the same thing.

As for an example of a basic optimization method, removing dead code, code that is in there but never called by the main method.

Another one is vector optimization, where certain routines or parts of routines where it's suitable use the vector units of a cpu to speed things up a little.

Re:Few Questions for any programmers (1)

walshy007 (906710) | more than 4 years ago | (#28568789)

bah, slashdot ate part of what I wrote, in the first line it is meant to be.

it optimizes the translation of "insert high level language here" to assembly opcodes

Re:Few Questions for any programmers (1)

contr0l (1590249) | more than 4 years ago | (#28568795)

Again, didnt even cross my mind. thanks alot. I would also be interested in taking a look at assembly, but all I hear about it is that is very hard to grasp, and not necessary with all the languages out there. But I will deff take a look into it to get a better idea.

Re:Few Questions for any programmers (4, Informative)

walshy007 (906710) | more than 4 years ago | (#28568829)

in regards to learning assembly, if you run linux, the best book I can recommend is Programming from the ground up [gnu.org] it's licensed under the GNU free documentation license, and in my honest opinion is likely the single best book for anyone who has no idea that wants to start, I already had some clue so skipped the first two thirds of the book, but read it for shits and giggles later and found it to be a very easy to grasp book.

To this day if I forget minor details about things I pick that back up and re-read it a bit :)

Re:Few Questions for any programmers (3, Insightful)

sydneyfong (410107) | more than 4 years ago | (#28569045)

Assembly itself is not "hard". The language itself is simple. I'd argue that most of the "hardness" is due to its simplicity. There is almost none of the abstract structures and methods that high level languages provide you, and even for something something as "simple" as calling a function, you'll have to manually push data on a stack, jump to the new location, and then pop back the data afterwards, etc.

Might be unnecessary for those programmers who has no interest in understanding how the computer actually works, but it's worth a look.

Disclaimer: I've never really done any assembly programming, but only "dabbled" in it for a bit a few years ago.

Re:Few Questions for any programmers (2, Insightful)

Another, completely (812244) | more than 4 years ago | (#28569081)

I agree that it's a good idea to learn assembly / machine language to understand what a compiler is doing, but learning the assembly language of the computer you use at home is not as reasonable a suggestion today as it once was. Learning to code to a 6802 wasn't bad; it only has a few instructions, and it's very instructive (and fun) to find out how many things you can do with just those. I think trying to write for your home PC in assembly is now beyond a beginner exercise though.

Microcontroller manufacturers often provide emulators and assemblers for their products, so you might download one of those to try. Then, when you get the hang of it, maybe a developer board and some 7-seg LEDs to build a calculator or something. Coding to this year's Intel chips is best left to the compilers and the mystics.

Anybody out there know a good emulator for teaching assembly programming?

Re:Few Questions for any programmers (2, Informative)

ZerothAngel (219206) | more than 4 years ago | (#28569227)

Anybody out there know a good emulator for teaching assembly programming?

SPIM [wisc.edu] is a possibility. It was used in a few courses (operating systems, compilers) at UCB some years ago. (Don't know if it's still used.)

Re:Few Questions for any programmers (1)

cbhacking (979169) | more than 4 years ago | (#28569983)

Yeah, it's still used. Of course, being a MIPS emulator, it's not exactly going to turn you into an amazing x86 optimizer, but it's a good ISA for learning simple assembly.

BeebEm (1)

Dr_Barnowl (709838) | more than 4 years ago | (#28569289)

BeebEm?

The BBC Micro came with an in-line assembler in the BASIC that shipped with the machine. The manual that came with it had a full reference for BASIC and 6502 assembler. It was a great machine for learning about computers ; lots of languages available, BASIC and assembler out of the box, and so many and varied I/O ports it was a hardware hackers dream as well. I remember the first time I patched in a routine that made the on board sound generate "key ticks" for each keystroke and being thrilled.

BBC BASIC was so good it's even been ported to Windows as a commercial product.... it still has the assembler, which now generates x86 opcodes instead.

The Spectrum used a Z80, and a lot more people were familiar with the assembly because of all the time devoted to poking games on it, but you needed a separate assembler to do any serious coding, like a Multiface with Genie. Rather more cumbersome, even if some people found the Z80 nicer to code for.

Re:Few Questions for any programmers (3, Interesting)

Anonymous Coward | more than 4 years ago | (#28568827)

Classic examples:
  • Replace a mod (e.g. x % 32) with a bitwise-and (e.g. x & 31) when the divisor is a power of two. Nearly every compiler does this now, but twenty years ago it was a common manual optimization trick.
  • Replace a branch with an arithmetic operation that yields the same result.

    i < 0 ? -i : i

    vs

    cdq
    xor eax, edx
    sub eax, edx

Re:Few Questions for any programmers (2, Informative)

EvanED (569694) | more than 4 years ago | (#28568863)

Replace a mod (e.g. x % 32) with a bitwise-and (e.g. x & 31) when the divisor is a power of two.

Another very similar one, and one that comes up more commonly, is the replacement of a multiplication or division by a constant by a series of additions, subtractions, and bitshifts.

For instance, "x/4" is the same as "x>>2", but the division at one point in time (and still with some compilers and no optimization) would produce code that ran slower. Some people still make this optimization by hand, but I'd say it's almost certainly a bad idea nowadays, at least in the absence of information that your compiler isn't optimizing it and that it would be important.

(You can combine operations too. x*7 is the same as x3-x, x*20 is the same as x4 + x2, etc.)

Re:Few Questions for any programmers (2)

EvanED (569694) | more than 4 years ago | (#28568915)

(You can combine operations too. x*7 is the same as x3-x, x*20 is the same as x4 + x2, etc.)

That should be
  x*7 == x << 3 - x
  x*20 == x << 4 + x << 2

Slashcode (somewhat reasonably) ate my <<s.

Re:Few Questions for any programmers (0)

Anonymous Coward | more than 4 years ago | (#28568979)

Did something else eat your parentheses?

Re:Few Questions for any programmers (1)

EvanED (569694) | more than 4 years ago | (#28568989)

No, I just got the precedence wrong. ;-)

In my post, pretend that << has a higher precedence than + and -.

Re:Few Questions for any programmers (2, Interesting)

TheRaven64 (641858) | more than 4 years ago | (#28569551)

Another very similar one, and one that comes up more commonly, is the replacement of a multiplication or division by a constant by a series of additions, subtractions, and bitshifts.

ARGH! Mod parent down! Please, please, please don't ever repeat this again to people asking things about optimisation. On most modern computers, shifts are slow. They are often even microcoded as multiplications, because they are incredibly rare in code outside segments where someone has decided to 'optimise'. Even when they're not, a typical CPU has more multiply units than shift units and the extra operations needed from the shift and add sequence bloat i-cache usage and cause pipeline stalls by adding adjacent dependencies. The 'optimised' version you describe will almost certainly be slower than the version using the multiply instruction.

I did some benchmarks with a Core 2 Duo a few months back of this exact optimisation and discovered that in the simplest case the add-and-shift version was as slow as the multiply, in any more complex case it was slower. There's a reason why GCC hasn't done this for some years.

Re:Few Questions for any programmers (2, Informative)

smallfries (601545) | more than 4 years ago | (#28569775)

No that's not true. A shift instruction has a one cycle latency and 1/2 cycle throughput on the Core2 / Core2-Duo. An add instruction also has a one cycle latency and 1/3 cycle throughput on the Core2-Duo.

The integer multiplier on the Core2-Duo has a 4-cycle throughput and an 8-cycle latency. So in a "simple" case like x*9 = (x<<3)+x the optimisation would take 2 cycles, and the straight mul would take 8. In more complex cases the individual shifts will pipeline for more of a benefit. Only in cases where (t/3)+ceil(lg(t)) >= 8 will the optimisation be as slow as the multiplier for an expansion of t terms (obviously logs in the base 2 as the additions will form a tree). On x86 lacks of registers will kill this optimisation before the cost of the instructions exceeds the multiplier cost.

And yes, I've also benchmarked the code to test it on a Core2-Duo, and my results match Intel's published figures and Agner Fog's data tables so I suggest you recheck your benchmark.

Getting back to the article, the Milepost work isn't really suitable for this type of optimisation anyway. They try and optimise the compile-time by tuning the optimisation flags. For this type of low-level tuning of code the approaches in Program Interpolation, Sketching or PetaBricks would be more appropriate.

Re:Few Questions for any programmers (1)

TheRaven64 (641858) | more than 4 years ago | (#28570217)

Note that microbenchmarks here don't tell the whole story, because the increase in cache churn, register pressure, and inter-instruction dependencies also slow things down. When you issue a set of shift and add instructions, each one has to complete, in order, before the next can start. With a multiply, this can be overlapped with load and store operations. A well-designed microbenchmark will show this to some degree, but in code where the multiply is close to other instructions it becomes even more obvious.

In more complex cases the individual shifts will pipeline for more of a benefit

This is absolutely and completely wrong. The dependencies between the shifts and adds mean that you get absolutely no benefit from pipelining; each one has to complete before the next can be issued. Worse, you cause a pipeline stall because you've just filled up the CPU's re-order buffer with shifts and adds and so you don't get any benefit from out-of-order execution either. Or from the chip's superscalar architecture; you can run several independent operations in parallel, but this sequence has to execute sequentially, giving about the worst case possible for throughput.

Don't just read the numbers from the architecture reference without understanding the chip design. They would give the performance you claim if the C2D was a single-pipeline, in-order CPU. They do not for an out-of-order superscalar design.

Re:Few Questions for any programmers (1)

SwabTheDeck (1030520) | more than 4 years ago | (#28570021)

Similarly, you can do integer division or multiplication by 2 as a bit shift, since a bit shift is a far less costly operation:

SHR EAX,1
instead of
DIV EAX,2

Re:Few Questions for any programmers (5, Informative)

Black Sabbath (118110) | more than 4 years ago | (#28568939)

Before you get flamed to death by some idiot, you've got realise that compilers translate a higher-level language into a lower-level one, typically into machine instructions (or in the case of Java and .NET, virtual machine instructions), turning source code into executable form. Interpreters on the other hand, execute each statement of the language directly (effectively forming a virtual machine for that language).

Naive compiler translations can be functionally correct but sub-optimal with respect to runtime performance, memory/disk footprint etc. Compiler optimisation is the effort to make this translation as optimal as possible with respect to some variable(s) e.g. performance, size

What you are thinking of sound like source code optimization. There are various interpretations of this but to my mind, this means a combination of optimal algorithm selection and optimal algorithm implementation. Note that complex algorithms can be decomposed into smaller common algorithms e.g. a sort routine may be part of some higher-level algorithm, the sort-routine may be optimised independently of the higher-level routine.

Check out: http://en.wikipedia.org/wiki/Compiler_optimization

Re:Few Questions for any programmers (1)

Karellen (104380) | more than 4 years ago | (#28570473)

"compilers translate a higher-level language into a lower-level one"

Not always [google.com] .

Actually, I'm fuzzy on which of Java or Javascript would be considered higher- or lower-level. It's not clear-cut, and could probably be considered more of a "sideways" shift than "downwards".

Re:Few Questions for any programmers (2, Informative)

symbolset (646467) | more than 4 years ago | (#28569047)

What things can a compiler do to your code to 'optimize' it for you?

The correct answer to this question is... it depends. No matter how advanced your compiler is it can't select the correct algorithm for you. If you're ordering your lists with a bubble sort instead of some kind of btree, there's nothing the compiler can do to help you except deliver the best O(n^2) sort it can. A truly artistic programmer can transcend all of the optimizations this compiler might achieve, by several orders of magnitude.

But if you're the kind of code geek that Microsoft hires, yeah, you might get a version of Windows that boots to a usable desktop in under five minutes.

Re:Few Questions for any programmers (1)

TheRaven64 (641858) | more than 4 years ago | (#28569589)

As a trivial example, one of the benchmarks I use for testing my Smalltalk compiler is a naive calculation of the Fibonacci sequence. With my first version, which did very little optimisation, it was much slower than GCC-compiled Objective-C (it's now about 50% slower). If, however, I compared a naive implementation in Objective-C to a more intelligent (O(n)) implementation in Smalltalk, the Smalltalk implementation was faster for all n greater than 30, and when you got closer to 40 it was several orders of magnitude faster. In most cases, a good algorithm with a bad compiler beats a good compiler with a bad algorithm.

I for one? (2, Funny)

Anenome (1250374) | more than 4 years ago | (#28568769)

Who would've guessed a compiler would become the first program to achieve sentience ;P

It will surely, er, program our programs to kill us.

Re:I for one? (5, Funny)

Norsefire (1494323) | more than 4 years ago | (#28568817)

It will surely, er, program our programs to kill us.

No, it'll just optimize out all emergency stop and safety routines. Humans inevitably die anyway so there is no point in slowing down the code to prevent it.

Re:I for one? (3, Funny)

EvanED (569694) | more than 4 years ago | (#28568935)

Humans inevitably die anyway so there is no point in slowing down the code to prevent it.

In fact, think of how much of an optimization that is! I mean, suppose people were killed by our robot overloads at 25. That's 1/3 of 75 years old; that's a 3x improvement in the speed we go through our life! In a world where a 20% improvement in speed for a new optimization is very impressive, 3x is just great!

hmmm... (0)

Anonymous Coward | more than 4 years ago | (#28570293)

What would really be nice is braindead coder elimination... first the compiler issues a warning, then it fires for effect.

John Connor?? (1)

Hansele (579672) | more than 4 years ago | (#28568775)

This was of course needed for the first build of Skynet. Learning compilers will then create "learning software". I for one welcome our new terminator-like overlords.

will they add clippy? (3, Insightful)

tbj61898 (643014) | more than 4 years ago | (#28569079)

It seems like You're computing a spatial Hash! Would You like to use the fastest subroutine I know or use your own?

seriously... this post talk about machine learning optimization, will it be like "more stuff You compile, better luck with resulting machine code" ?

It's like a new GPS navigation software thats not only capable of route optimization but also capable of destination suggestions. "It sounds like You're going to a grocery store to buy pizza... there's a pizza hut round the corner!"

Gentoo (1)

karstux (681641) | more than 4 years ago | (#28569097)

So if I'd compile a Linux from scratch with this new compiler, everything speeds up by 18% on average? That would be quite impressive, and possibly the best justification for Gentoo. Might be nice for my aging notebook...

Re:Gentoo (0)

Anonymous Coward | more than 4 years ago | (#28569263)

Maybe everything except compile times...

And so Skynet was born. (0)

Anonymous Coward | more than 4 years ago | (#28569391)

Inevitable, as we all know you cannot change the past or the future.

The Ultimate Test... (0)

Anonymous Coward | more than 4 years ago | (#28569691)

Is if it could optimize itself to make it a better optimized compiler?

Summary is extremely misleading (3, Informative)

Skuto (171945) | more than 4 years ago | (#28569757)

>The compiler is expected to significantly reduce time-to-market of new software,
>because lengthy manual optimization can now be carried out by the compiler.

The time to *make a new compiler* for a certain processor is reduced, and the
process of figuring which optimizations are should be in the compiler for that architecture
is automated.

This is for the kind of research where they attempt to make many specialized processors
on a single chip instead of a general monolithic one. In this case, you need many
compilers and tuning those is important. It's the time optimizing THOSE that is lowered,
not the one of writing the software that is compiled itself.

I see no real relevance to the "normal" desktop situation on that website.

Re:Summary is extremely misleading (1)

Fullers (1590483) | more than 4 years ago | (#28570101)

Actually the time to make a new compiler is reduced *and* the optimization performance of the compiler increased when compared to standard GCC (whichis what the 18% refers to). Therefore 'normal' desktop use is a real possibility.

Re:Summary is extremely misleading (1)

Skuto (171945) | more than 4 years ago | (#28570287)

>Actually the time to make a new compiler is
>reduced *and* the optimization performance of the
>compiler increased when compared to standard GCC
>(whichis what the 18% refers to).

Yes, 18% performance increase on an IBM p system running an embedded application benchmark. Ahem. Let's not talk about the compilation time, either.

It seems to be basically a very smart way to find the optimal combination of gcc optimization flags.

Now, how this will achieve:

"The compiler is expected to significantly reduce time-to-market of new software, because lengthy manual optimization can now be carried out by the compiler."

It won't. The summary is complete bollocks.

Re:Summary is extremely misleading (1)

Fullers (1590483) | more than 4 years ago | (#28570311)

The summary is complete bollocks.

How do you know? It seems entirely plausible to me that significantly better compiler optimization could reduce the level of manual optimization needed for embedded systems, and thus reduce the time-to-market.

Better RAID controllers! Better routers! (1)

FranTaylor (164577) | more than 4 years ago | (#28569885)

I can see how this could lead to very fast, very cheap RAID controllers.

Also, imagine if those cheap little gigabit switches were actually 8-port gigabit Routers.

This is the sort of thing you can do with this technology.

mo3 3own (-1, Flamebait)

Anonymous Coward | more than 4 years ago | (#28570093)

Darren Reed, which Lite is straining members' creative the public eye: you should bring = 1400 NetBSD I won't bore you Look at your soft, all; in order to go tangle of fatal is busy infighting distributions bloc in order to Minutes. If that. and enjoy all the

"Lengthy manual optimization"? (1)

John Hasler (414242) | more than 4 years ago | (#28570343)

> The compiler is expected to significantly reduce time-to-market of new software, because
> lengthy manual optimization can now be carried out by the compiler.

I always thought that testing and debugging were the lengthy manual steps. Oh. Wait. "Time to market". They're talking about proprietary software. Never mind.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...