Re: Bitshifts and And vs Floor-division and Modular
On 07/09/2012 02:08, Cameron Simpson wrote: On 07Sep2012 01:30, Mark Lawrence breamore...@yahoo.co.uk wrote: | On 07/09/2012 01:01, jimbo1qaz wrote: | Is it faster to use bitshifts or floor division? And which is better, or %? | All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? | | Why don't you use the timeit module and find out for yourself? Because timeit doesn't output style advice? Because timeit won't offer even a short single parapgraph description of how python ints (even just in CPython) are implemented and how that may affect performance in general? To the OP: personally, I would suggest using % when I am thinking of division and a bit shift when I am thinking of a bitshift, and only reach for timeit when performance becomes an issue. Code for the algoritm, and only optimise later. Of course only a well run benchmark will measure the real world, but it possible to address his other questions in a helpful fashion and address the benchmark question in a less offputting tone. If you can't be bothered, please don't. (Especially since these irritating posts from you are usually in response to a post you feel could have used more effort from the OP.) Nobody answers all performance considerations or design choices with an exhaustive timeit benchmark, and it is silly to suggest so. It is helpful for people to have a mental model of the python internals so they can make often-sensible choices from the start. So try being helpful instead of slapping people down when they haven't reached your private bar. Cheers, I'm sorry but I refuse point blank to spoon feed, fit bibs and change nappies. I wouldn't do that on the tutor mailing list and I certainly wouldn't do it here. If any OP is too bone idle to do some research and then pose a sensible question relating to what they want to achieve, what they've done to achieve it and what issues they've got then I intend responding in the same way. Clearly your approach is different so we'll have to agree to disagree. -- Cheers. Mark Lawrence. -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On 2012-09-07, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: My *guess* is that you mean *bitwise* operators, compared to numeric operators like * and // (integer division). The runtime cost is mostly dominated by the object-oriented overhead -- Python is not C or assembly, and the integers are rich objects, not low-level bitfields, so the difference between division and bitshifting is much less than you might expect from assembly language. I don't suppose there's much of a chance that the OP is running Python on a CPU that doesn't have an integer divide instruction? If that _were_ the case, the difference would be more noticable, but would still probably not worth worrying about unless a truely huge number of operations were being done in a very tight loop with no intervening I/O operations. -- Grant Edwards grant.b.edwardsYow! I have accepted at Provolone into my life! gmail.com -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On Sep 7, 9:32 am, Paul Rubin no.em...@nospam.invalid wrote: rusi rustompm...@gmail.com writes: On an 8086/8088 a MUL (multiply) instruction was of the order of 100 clocks ... On most modern processors (after the pentium) the difference has mostly vanished. I cant find a good data sheet to quote though See http://www.agner.org/optimize/: Hey Thanks! Seems like a nice resource! How on earth does he come up with the data though, when Intel does not publish it? -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On 09/07/2012 12:59 PM, rusi wrote: On Sep 7, 9:32 am, Paul Rubin no.em...@nospam.invalid wrote: rusi rustompm...@gmail.com writes: On an 8086/8088 a MUL (multiply) instruction was of the order of 100 clocks ... On most modern processors (after the pentium) the difference has mostly vanished. I cant find a good data sheet to quote though See http://www.agner.org/optimize/: Hey Thanks! Seems like a nice resource! How on earth does he come up with the data though, when Intel does not publish it? As he says on the home page, he measured the data himself. Unclear how repeatable such data may be, either due to environment or to multiple versions of the processor, and from two vendors. -- DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On 07/09/2012 01:01, jimbo1qaz wrote: Is it faster to use bitshifts or floor division? And which is better, or %? All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? Why don't you use the timeit module and find out for yourself? -- Cheers. Mark Lawrence. -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On Thursday, September 6, 2012 5:30:05 PM UTC-7, Mark Lawrence wrote: On 07/09/2012 01:01, jimbo1qaz wrote: Is it faster to use bitshifts or floor division? And which is better, or %? All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? Why don't you use the timeit module and find out for yourself? -- Cheers. Mark Lawrence. How do I use it? timeit.timer is not defined. -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On 07Sep2012 01:30, Mark Lawrence breamore...@yahoo.co.uk wrote: | On 07/09/2012 01:01, jimbo1qaz wrote: | Is it faster to use bitshifts or floor division? And which is better, or %? | All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? | | Why don't you use the timeit module and find out for yourself? Because timeit doesn't output style advice? Because timeit won't offer even a short single parapgraph description of how python ints (even just in CPython) are implemented and how that may affect performance in general? To the OP: personally, I would suggest using % when I am thinking of division and a bit shift when I am thinking of a bitshift, and only reach for timeit when performance becomes an issue. Code for the algoritm, and only optimise later. Of course only a well run benchmark will measure the real world, but it possible to address his other questions in a helpful fashion and address the benchmark question in a less offputting tone. If you can't be bothered, please don't. (Especially since these irritating posts from you are usually in response to a post you feel could have used more effort from the OP.) Nobody answers all performance considerations or design choices with an exhaustive timeit benchmark, and it is silly to suggest so. It is helpful for people to have a mental model of the python internals so they can make often-sensible choices from the start. So try being helpful instead of slapping people down when they haven't reached your private bar. Cheers, -- Cameron Simpson c...@zip.com.au Microsoft: Where do you want to go today? UNIX: Been there, done that! -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On Thursday, September 6, 2012 5:01:12 PM UTC-7, jimbo1qaz wrote: Is it faster to use bitshifts or floor division? And which is better, or %? All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? OK, I decided to change my code. Which raises a similar question: Which one is better for setting a bit of a byte: |= or +=, assuming each will only be run once? Intuitively, I think |=, but some timeits are inconclusive, mainly because I don't know how it works. -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On 09/06/2012 08:01 PM, jimbo1qaz wrote: Is it faster to use bitshifts or floor division? Yes, and yes. Without doing any measurement, I'd expect that in CPython, it makes negligible performance difference for ordinary ints (under 2**31, more or less). Ordinary ints can be done with single instructions, and any such instruction would be a tiny fraction of the opcode overhead. One place were there might be a difference would be for longs. The implementation of those would have to be a loop, and eventually one might be faster than the other. At that point, maybe you'd want to measure. And which is better, or %? All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? The better way is not the faster one, but rather is the one that more clearly expresses the original problem. If the problem is a modulo one, use % (or frequently divmod). If the problem is a bit shift/masking one, then use such operators. BTW, '/' on integers is redefined for Python 3.x to give float results, and not to truncate. -- DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On 09/06/2012 09:30 PM, jimbo1qaz wrote: On Thursday, September 6, 2012 5:01:12 PM UTC-7, jimbo1qaz wrote: Is it faster to use bitshifts or floor division? And which is better, or %? All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? OK, I decided to change my code. Which raises a similar question: Which one is better for setting a bit of a byte: |= or +=, assuming each will only be run once? Intuitively, I think |=, but some timeits are inconclusive, mainly because I don't know how it works. Maybe i should have been clearer in my message. i don't think you'll find a meaningful difference unless you're doing longs of a few hundred digits. So if the algorithm is to OR on a bit, please use a |= augmented assignment. not only will it ward off probable bugs when you accidentally try to set the bit a second time, but it reads better for the reader of the program. The reader is more important than the compiler. -- DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On 9/6/2012 8:01 PM, jimbo1qaz wrote: Is it faster to use bitshifts or floor division? And which is better, or %? All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? Yes, meaningless, yes, and no. I would do what seems sensible to you in the context. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On Thu, 06 Sep 2012 17:01:12 -0700, jimbo1qaz wrote:
Is it faster to use bitshifts or floor division?
Does it matter?
If you ever find yourself writing an application where the difference
between 0.0476 microseconds and 0.0473 microseconds matters to you,
Python is probably the wrong language.
py from timeit import Timer
py min(Timer('456789 // 8').repeat(repeat=35))
0.04760909080505371
py min(Timer('456789 3').repeat(repeat=35))
0.047319889068603516
And which is better, or %?
Depends what you want to do. If you want to perform bitwise-and, then I
strongly recommend you use , the bitwise-and operator. If you want to
perform modulus, then the modulus operator % is usually better.
All divisors and mods are power of 2, so are binary operations
faster?
As the MiddleMan says, specificity is the soul of all good
communication. Python has many binary operations, e.g.:
+ - * / // % == is = = ** ^ |
Some of them are faster than some other things, so would you like to be
more specific?
My *guess* is that you mean *bitwise* operators, compared to numeric
operators like * and // (integer division). The runtime cost is mostly
dominated by the object-oriented overhead -- Python is not C or assembly,
and the integers are rich objects, not low-level bitfields, so the
difference between division and bitshifting is much less than you might
expect from assembly language.
But, in principle at least, there *may* be some tiny advantage to the
bitwise operators. I say may because the difference is so small that it
is likely to be lost in the noise. I do not believe that there will be
any real world applications where the difference between the two is
significant enough to care about. But if you think different, feel free
to use the profile module to profile your code and demonstrate that
divisions are a significant bottleneck in your application.
And are they considered bad style?
Absolutely. Using when you mean to take the remainder is a dirty
optimization hack only justified if you really, really, really need it.
I'm pretty confident that you will never notice a speed-up of the order
of 0.1 nanoseconds.
More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason — including
blind stupidity. — W.A. Wulf
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%. A good programmer will not be
lulled into complacency by such reasoning, he will be wise to look
carefully at the critical code; but only after that code has been
identified — Donald Knuth
Bottlenecks occur in surprising places, so don't try to second guess and
put in a speed hack until you have proven that's where the bottleneck
is. — Rob Pike
The First Rule of Program Optimization: Don't do it. The Second Rule of
Program Optimization (for experts only!): Don't do it yet. — Michael A.
Jackson
--
Steven
--
http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On Thu, 06 Sep 2012 18:30:48 -0700, jimbo1qaz wrote: OK, I decided to change my code. Which raises a similar question: Which one is better for setting a bit of a byte: |= or +=, assuming each will only be run once? Intuitively, I think |= Python (like most languages) doesn't have a set this bit operator, so the closest match is a bitwise-or. So to set a bit of a byte, the operation which most closely matches the programmer's intention is to use the bitwise operator. Even better would be to write a function called setBit, and use that. but some timeits are inconclusive, Timing results are usually inconclusive because the difference between the results are much smaller than that average random noise on any particular result. All modern computers, say for the last 20 or 30 years, have used multitasking operating systems. This means that at any time you could have dozens, even hundreds, of programs running at once, with the operating system switching between them faster than you can blink. In addition, the time taken by an operation can depend on dozens of external factors, such as whether the data is already in a CPU cache, whether CPU prediction has pre-fetched the instructions needed, pipelines, memory usage, latency when reading from disks, and many others. Consequently, timing results are very *noisy* -- the *exact* same operation can take different amount of time from one run to the next. Sometimes *large* differences. So any time you time a piece of code, what you are *actually* getting is not the amount of time that code takes to execute, but something slightly more. (And, occasionally, something a lot more.) Note that it is always slightly more -- by definition, it will never be less. So if you want a better estimate of the actual time taken to execute the code, you should repeat the measurement as many times as you can bear, and pick the smallest value. *Not* the average, since the errors are always positive. An average just gives you the true time plus some unknown average error, which may not be small. The minimum gives you the true time plus some unknown but hopefully small error. The smaller the amount of time you measure, the more likely that it will be disrupted by some external factor. So timeit takes a code snippet and runs it many times (by default, one million times), and returns the total time used. Even if one or two of those runs were blown out significantly, the total probably won't be. (Unless of course your anti-virus decided to start running, and *everything* slows down for 10 minutes, or something like that.) But even that total time returned by timeit is almost certainly wrong. So you should call the repeat method, with as many iterations as you can bear to wait for, and take the minimum, which will still be wrong but it will be less wrong. And remember, the result you get is only valid for *your* computer, running the specific version of Python you have, under the specific operating system. On another computer with a different CPU or a different OS, the results may be *completely* different. Are you still sure you care about shaving off every last nanosecond? mainly because I don't know how it works. The internal details of how timeit works are complicated, but it is worth reading the comments and documentation, both in the Fine Manual and in the source code: http://docs.python.org/library/timeit.html http://hg.python.org/cpython/file/2.7/Lib/timeit.py -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
On Sep 7, 5:01 am, jimbo1qaz jimmyli1...@gmail.com wrote: Is it faster to use bitshifts or floor division? And which is better, or %? All divisors and mods are power of 2, so are binary operations faster? And are they considered bad style? On an 8086/8088 a MUL (multiply) instruction was of the order of 100 clocks and a DIV nearly 200 compared to ADD, OR etc which were something like 8 (IIRC -- this is decades-stale knowledge) On most modern processors (after the pentium) the difference has mostly vanished. I cant find a good data sheet to quote though -- one of the sad things about modern processors is that the clocks which were politely offered by intel earlier have now stopped presumably because cache-(in)coherence, pipelining etc are more likely to dominate the number of clocks than the specific instruction. This question is interesting to a programmer but meaningless at the python level (as others have pointed out). If it still interests you, work at the C (or still better assembly) level and use a more finegrained timer measure -- the finest being the RDTSC instruction. -- http://mail.python.org/mailman/listinfo/python-list
Re: Bitshifts and And vs Floor-division and Modular
rusi rustompm...@gmail.com writes: On an 8086/8088 a MUL (multiply) instruction was of the order of 100 clocks ... On most modern processors (after the pentium) the difference has mostly vanished. I cant find a good data sheet to quote though See http://www.agner.org/optimize/ : 4. Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs Multiplication is now fast but DIV is still generally much slower. There are ways to make fast parallel dividers that I think nobody bothers with, because of chip area and because one can often optimize division out of algorithms, replacing most of it with multiplication. Worrying about this sort of micro-optimization in CPython is almost always misplaced, since the interpreter overhead generally swamps any slowness of the machine arithmetic. -- http://mail.python.org/mailman/listinfo/python-list
