Re: [OT] Bit twiddling homework

[Peter J. Holzer]

On 2018-07-20 19:13:44 +1000, Chris Angelico wrote:
> On Fri, Jul 20, 2018 at 7:00 PM, Brian Oney via Python-list
>  wrote:
> > That's right I had forgotten about that. Thank you for the quick 
> > answer.Some fun:$ ipythonPython 2.7.13 (default, Nov 24 2017, 17:33:09) 
> > ...In [1]: j = 16; i = 1
> > In [2]: print(i+j); print(i|j)1717
> > In [3]: %timeit i+j1000 loops, best of 3: 65.8 ns per loop
> > In [4]: %timeit i|j1000 loops, best of 3: 73 ns per loop
> > In [5]: %timeit 16|11000 loops, best of 3: 28.8 ns per loop
> > In [6]: %timeit 16+11000 loops, best of 3: 28.8 ns per loop
> > I wonder why the difference between [3] and [4]. My mental ranking of speed 
> > of operations tells me it should be the other way around.
> > Are 16|1 and 16+1 internally the same operation (for integers)?
> 
> What you're seeing is nothing but noise. With numbers this low, you
> can't really judge anything.

Also, Brian is timing Python operations here, not CPU operations. In
order to execute an arithmetic or logical operation, the Python
interpreter has to execute dozens or hundreds of CPU operations. So the
single ADD or OR somewhere in the middle is swamped by other
instructions.

It is possible that the code performing a numeric addition is a bit
better optimized than the code performing a bitwise or. But looking at
the source code that doesn't seem to be the case.

Might be just an accident, although the difference is remarkably
reproducible.

Anybody have a CPU emulator handy to trace this clock by clock? ;-)

hp

-- 
   _  | Peter J. Holzer| we build much bigger, better disasters now
|_|_) || because we have much more sophisticated
| |   | h...@hjp.at | management tools.
__/   | http://www.hjp.at/ | -- Ross Anderson 


signature.asc
Description: PGP signature
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[jladasky]

On Friday, July 20, 2018 at 2:00:26 AM UTC-7, Brian Oney wrote:

> Are 16|1 and 16+1 internally the same operation (for integers)?

For 16 and 1, the output of the two operations happen to be the same, but 
generally a bitwise OR is not the same are addition.  There are no carry bits 
in the bitwise operation!  1 + 1 = 2.  But 1 | 1 = 1.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Grant Edwards]

On 2018-07-20, Chris Angelico  wrote:
> On Sat, Jul 21, 2018 at 1:14 AM, Grant Edwards  
> wrote:
>> On 2018-07-20, Dennis Lee Bieber  wrote:
>>
>>> While I suspect Python isn't micro-optimizing, take into account
>>> that most processors do have an "increment"/"decrement" operation --
>>> since that is done so much at the low-level. Also, just general
>>> integer addition is common, so the hardware may be optimized for
>>> doing them fast. Boolean operations may not be as well optimized.
>>
>> Boolean operations are also very common at the lowest level, and they
>> involve far simpler logic than does addition.  I refuse to believe
>> there's an extant processor in common use where an ADD is faster than
>> an OR unless somebody shows me the processor spec sheet.
>
> "Faster than"? I'd agree with you.

My understanding was that the hypothesis was the Python benchmark
discrepency might be due to the CPU ADD operation being faster than
the OR operator.

> But "as fast as"?  I believe that's how most modern CPUs already
> operate. (Well, mostly.) There are sophisticated methods of
> daisy-chaining the carry bit that mean the overall addition can be
> performed remarkably quickly, and the end result is a one-clock ADD
> operation, same as OR.

Definitely.  Any modern CPU capable of running Python will have single
cycle add/subtract/or/and/not/xor.  Addition is so important for so
many things that they will have jumped through the hoops required to
build a single cycle word-width adder.  And/or/not is so simple
there's just no sane way to make it take more than one cycle.

> For most data, most code, and most situations, integer addition is
> exactly as fast as integer bit shift.

Yes.

-- 
Grant Edwards   grant.b.edwardsYow! Was my SOY LOAF left
  at   out in th'RAIN?  It tastes
  gmail.comREAL GOOD!!

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Chris Angelico]

On Sat, Jul 21, 2018 at 2:39 AM, Marko Rauhamaa  wrote:
> Chris Angelico :
>
>> On Sat, Jul 21, 2018 at 1:14 AM, Grant Edwards
>>  wrote:
>>> I refuse to believe there's an extant processor in common use where
>>> an ADD is faster than an OR unless somebody shows me the processor
>>> spec sheet.
>>
>> "Faster than"? I'd agree with you. But "as fast as"? I believe that's
>> how most modern CPUs already operate. (Well, mostly.) There are
>> sophisticated methods of daisy-chaining the carry bit that mean the
>> overall addition can be performed remarkably quickly, and the end
>> result is a one-clock ADD operation, same as OR. For most data, most
>> code, and most situations, integer addition is exactly as fast as
>> integer bit shift.
>
> I'm guessing the clock speed is adjusted for the longest propagation
> delays. According to
>
>https://en.wikipedia.org/wiki/Carry-lookahead_adder#Implementa
>tion_details>
>
> the maximal gate delay of a 16-bit carry-lookahead-adder is 8 gate
> delays. A 64-bit addition results in some more delay:
>
>https://en.wikipedia.org/wiki/Lookahead_carry_unit#64-bit_adder>

Right; and since "one clock" is sufficient to propagate through all
the gates of a 64-bit snake (err, I mean adder), and since "one clock"
is also the shortest time from one instruction to the next, the
bitwise operation and the arithmetic operation will generally take the
same amount of time. Generally.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Marko Rauhamaa]

Chris Angelico :

> On Sat, Jul 21, 2018 at 1:14 AM, Grant Edwards
>  wrote:
>> I refuse to believe there's an extant processor in common use where
>> an ADD is faster than an OR unless somebody shows me the processor
>> spec sheet.
>
> "Faster than"? I'd agree with you. But "as fast as"? I believe that's
> how most modern CPUs already operate. (Well, mostly.) There are
> sophisticated methods of daisy-chaining the carry bit that mean the
> overall addition can be performed remarkably quickly, and the end
> result is a one-clock ADD operation, same as OR. For most data, most
> code, and most situations, integer addition is exactly as fast as
> integer bit shift.

I'm guessing the clock speed is adjusted for the longest propagation
delays. According to

   https://en.wikipedia.org/wiki/Carry-lookahead_adder#Implementa
   tion_details>

the maximal gate delay of a 16-bit carry-lookahead-adder is 8 gate
delays. A 64-bit addition results in some more delay:

   https://en.wikipedia.org/wiki/Lookahead_carry_unit#64-bit_adder>


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Brian Oney via Python-list]

On Fri, 2018-07-20 at 10:38 -0400, Dennis Lee Bieber wrote:
> On Fri, 20 Jul 2018 11:00:09 +0200, Brian Oney via Python-list
>  declaimed the following:
> 
> > Are 16|1 and 16+1 internally the same operation (for integers)? 
> 
>   For those integers the EFFECT/RESULT will be the same. But...
> 
> > > > 17 + 1
> 
> 18
> > > > 17 | 1
> 
> 17
Of course. There was a reason I chose those integers and timed them. I am 
ignorant of how Python stores an integer internally. Either way (2^x bit) the 
result would be the same regardless.
In retrospect, I seem to suggest that Python would have different sets of 
operations for an integer based on it's value; that's poor wording. Anyways.
 
> {From the original post}
> > For example, bitwise operators are neat (here a shift):
> > C:
> >  int res = 1 << 4 
> >  printf("%d\n", res)
> > 16
> > 
> > Translates to pseudocrap:
> >  0001 -> leftwards bitshift of 4 places -> 0001 
> > 
> 
>   Python also supports shift...
> 
> > > > 17 << 2
> 
> 68
> > > > 17 >> 2
> 
> 4
Nice! Once again Python shines as a prototyping language!
> [Side comment, even in C bitwise operators aren't really considered playing
> "directly with memory". That would be more something like:
> 
>   int * i;// i is a pointer (address) to an 
> integer
>   i = 0x01FF; // set i to access address 511
>   printf("%d\n", *i); // print (as integer) whatever is stored at 511
> 
> THAT you can not do in Python (at least, not without using something like
> the ctypes library).]
> 
Thank you for the explanation. That is a nice example.
>   Hex is basically just a means of shortening a binary string by
> representing runs of 4 bits using a single symbol. Same with Octal (runs of
> 3 bits). In both cases, each symbol translates to an integral number of
> bits, and position in a multi-symbol value can be translated directly.
> 
>   This is not possible when representing binary values in Decimal, as
> each place in the decimal representation does not map to an integral number
> of bits.
> 
Yup! Wikipedia has the same info scattered about the hexadecimal page. You 
describe it nicely from the perspective of a computer scientist.
> > Therefore, what book or learning course do you recommend? I imagine 
> > something that tours or skims
> > the fundamentals of Boolean algebra and digital logic, and then goes to C 
> > and some fun homework
> > problems. It may seem to you that the emphasis there is wrongly placed. 
> 
>   While Boolean algebra and digital logic are core concepts for
> computers, neither really appear in books that teach programming. Boolean
> logic is more in the realms of pure math and then feeds to digital logic
> (at the gate level -- NAND, NOR, AND, OR gates and combinations to create
> things like adders). Consider de Morgan's theorem:
> 
> A & B =>  not(not A | not B)
> A | B =>  not(not A & not B)
> 
> > > > b = 24
> > > > a = 19
> > > > a & b
> 
> 16
> > > > a | b
> 
> 27
> > > > a ^ b
> 
> 11
> > > > ~(~a & ~b)
> 
> 27
> > > > ~(~a | ~b)
> 
> 16
Thank you for the advice. Those are also some nice examples. Cool, I can do 
this stuff in Python. I guess this is also why Python is so popular; an 
instructor can take one language and cover a ton of material without having to 
saddle students with learning another language.
>   Can't really help with suggesting books -- The ones from my college
> days are likely out-of-print; I haven't really had a need to buy newer
> books for such basic concepts. Even simple discrete 74xx chips are so rare
> these days that the idea of creating a four-bit ADDER from gates is hard to
> find.
> 
>   Parallax used to have a slew of educational stuff based on BASIC Stamps
> and a logic simulator (and project board), but neither appear to still be
> in their catalog (the books used to be available as PDF for most of their
> educational stuff). I did find a copy on a third-party site for the Digital
> Logic intro
> http://rambal.com/index.php?controller=attachment_attachment=686=AOvVaw3YI9p_blIFAgardqgB2SBq
> 
> Can't find a download for their logical simulator, but there is something
> that might be usable at 
> https://sourceforge.net/projects/cedarlogic/
> 
> 
>   Just to put this back on topic for the group...
> 
>   Pretty much all of what you ask can be learned in Python (and using the
> interactive interpreter is a lot faster than writing a C program, compiling
> it, etc. -- as can be seen by the cut examples above). It is only
> direct hardware access that is not something Python is really suited for
> (although AdaFruit has a few boards which run CircuitPython
> [MicroPython+special libraries] if you really want to play with LEDs and
> such -- though they still don't access raw memory). If you really want
> hardware access -- as in the processor registers, memory, etc. -- you are
> probably talking about something like Arduino (AVR for Uno/Mega; ARM for
> Due), 

Re: [OT] Bit twiddling homework

[Chris Angelico]

On Sat, Jul 21, 2018 at 1:14 AM, Grant Edwards
 wrote:
> On 2018-07-20, Dennis Lee Bieber  wrote:
>
>> While I suspect Python isn't micro-optimizing, take into account
>> that most processors do have an "increment"/"decrement" operation --
>> since that is done so much at the low-level. Also, just general
>> integer addition is common, so the hardware may be optimized for
>> doing them fast. Boolean operations may not be as well optimized.
>
> Boolean operations are also very common at the lowest level, and they
> involve far simpler logic than does addition.  I refuse to believe
> there's an extant processor in common use where an ADD is faster than
> an OR unless somebody shows me the processor spec sheet.
>

"Faster than"? I'd agree with you. But "as fast as"? I believe that's
how most modern CPUs already operate. (Well, mostly.) There are
sophisticated methods of daisy-chaining the carry bit that mean the
overall addition can be performed remarkably quickly, and the end
result is a one-clock ADD operation, same as OR. For most data, most
code, and most situations, integer addition is exactly as fast as
integer bit shift.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Grant Edwards]

On 2018-07-20, Dennis Lee Bieber  wrote:

> While I suspect Python isn't micro-optimizing, take into account
> that most processors do have an "increment"/"decrement" operation --
> since that is done so much at the low-level. Also, just general
> integer addition is common, so the hardware may be optimized for
> doing them fast. Boolean operations may not be as well optimized.

Boolean operations are also very common at the lowest level, and they
involve far simpler logic than does addition.  I refuse to believe
there's an extant processor in common use where an ADD is faster than
an OR unless somebody shows me the processor spec sheet.

-- 
Grant Edwards   grant.b.edwardsYow! These PRESERVES should
  at   be FORCE-FED to PENTAGON
  gmail.comOFFICIALS!!

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Brian Oney via Python-list]

On Fri, 2018-07-20 at 18:07 +0900, xffox wrote:
> On Fri, Jul 20, 2018 at 08:25:04AM +0200, Brian Oney via Python-list wrote:
> > Therefore, what book or learning course do you recommend? I imagine 
> > something that tours or skims
> > the fundamentals of Boolean algebra and digital logic, and then goes to C 
> > and some fun homework
> > problems. It may seem to you that the emphasis there is wrongly placed. 
> 
> "Hacker's Delight" (please don't judge by the name):
> https://en.wikipedia.org/wiki/Hacker's_Delight . It's a collection of
> bit-level hacks. Figuring out each trick before reading the solution can
> provide a list of fun homework problems. Hope it helps.
That's what I am looking for. Thank you so much. Have a nice weekend!
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Ben Bacarisse]

Brian Oney  writes:

> On Fri, 2018-07-20 at 06:37 +, Steven D'Aprano wrote:
>> On Fri, 20 Jul 2018 08:25:04 +0200, Brian Oney via Python-list wrote:
>> 
>> > PS: Can I twiddle bits in Python?
>> 
>> Yes.
>> 
>> These operators work on ints:
>> 
>>   bitwise AND:  &
>>   bitwise OR:   |
>>   bitwise XOR:  ^
>> 
> That's right I had forgotten about that.

There's also ~ for bitwise negation.  Rather than explain what this
means in a language with an unbounded integer type, you might like to
experiment, er, a bit.  (Excuse the pun.)

-- 
Ben.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Chris Angelico]

On Fri, Jul 20, 2018 at 7:00 PM, Brian Oney via Python-list
 wrote:
> On Fri, 2018-07-20 at 06:37 +, Steven D'Aprano wrote:
>> On Fri, 20 Jul 2018 08:25:04 +0200, Brian Oney via Python-list wrote:
>>
>> > PS: Can I twiddle bits in Python?
>>
>> Yes.
>>
>> These operators work on ints:
>>
>>   bitwise AND:  &
>>   bitwise OR:   |
>>   bitwise XOR:  ^
>>
> That's right I had forgotten about that. Thank you for the quick answer.Some 
> fun:$ ipythonPython 2.7.13 (default, Nov 24 2017, 17:33:09) ...In [1]: j = 
> 16; i = 1
> In [2]: print(i+j); print(i|j)1717
> In [3]: %timeit i+j1000 loops, best of 3: 65.8 ns per loop
> In [4]: %timeit i|j1000 loops, best of 3: 73 ns per loop
> In [5]: %timeit 16|11000 loops, best of 3: 28.8 ns per loop
> In [6]: %timeit 16+11000 loops, best of 3: 28.8 ns per loop
> I wonder why the difference between [3] and [4]. My mental ranking of speed 
> of operations tells me it should be the other way around.
> Are 16|1 and 16+1 internally the same operation (for integers)?

What you're seeing is nothing but noise. With numbers this low, you
can't really judge anything. In fact, operations 5 and 6 are probably
just looking up constants that got calculated once, so they're
literally proving nothing at all.

Even at the CPU level, you'll generally find that adding two numbers
takes the same amount of time as bitwise Or, mainly because both of
them take a single clock cycle. (Proving that they actually DON'T take
the same amount of time requires a fairly deep understanding of the
internal workings of the chip.) Definitely at the Python level, the
costs are virtually identical. Don't do bitwise operations for the
sake of performance; do them because they clearly and adequately
describe what you're doing. :)

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[xffox]

On Fri, Jul 20, 2018 at 08:25:04AM +0200, Brian Oney via Python-list wrote:
> Therefore, what book or learning course do you recommend? I imagine something 
> that tours or skims
> the fundamentals of Boolean algebra and digital logic, and then goes to C and 
> some fun homework
> problems. It may seem to you that the emphasis there is wrongly placed. 

"Hacker's Delight" (please don't judge by the name):
https://en.wikipedia.org/wiki/Hacker's_Delight . It's a collection of
bit-level hacks. Figuring out each trick before reading the solution can
provide a list of fun homework problems. Hope it helps.
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Brian Oney via Python-list]

On Fri, 2018-07-20 at 06:37 +, Steven D'Aprano wrote:
> On Fri, 20 Jul 2018 08:25:04 +0200, Brian Oney via Python-list wrote:
> 
> > PS: Can I twiddle bits in Python?
> 
> Yes.
> 
> These operators work on ints:
> 
>   bitwise AND:  &
>   bitwise OR:   |
>   bitwise XOR:  ^
> 
That's right I had forgotten about that. Thank you for the quick answer.Some 
fun:$ ipythonPython 2.7.13 (default, Nov 24 2017, 17:33:09) ...In [1]: j = 16; 
i = 1
In [2]: print(i+j); print(i|j)1717
In [3]: %timeit i+j1000 loops, best of 3: 65.8 ns per loop
In [4]: %timeit i|j1000 loops, best of 3: 73 ns per loop
In [5]: %timeit 16|11000 loops, best of 3: 28.8 ns per loop
In [6]: %timeit 16+11000 loops, best of 3: 28.8 ns per loop
I wonder why the difference between [3] and [4]. My mental ranking of speed of 
operations tells me it should be the other way around.
Are 16|1 and 16+1 internally the same operation (for integers)? 
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Steven D'Aprano]

On Fri, 20 Jul 2018 08:25:04 +0200, Brian Oney via Python-list wrote:

> PS: Can I twiddle bits in Python?

Yes.

These operators work on ints:

  bitwise AND:  &
  bitwise OR:   |
  bitwise XOR:  ^



-- 
Steven D'Aprano
"Ever since I learned about confirmation bias, I've been seeing
it everywhere." -- Jon Ronson

-- 
https://mail.python.org/mailman/listinfo/python-list

Re: [OT] Bit twiddling homework

[Chris Angelico]

On Fri, Jul 20, 2018 at 4:25 PM, Brian Oney via Python-list
 wrote:
> PS: Can I twiddle bits in Python?

You sure can! With most of the same operators that you would in C. The
main difference is that Python's integers don't have word size limits;
instead of working with, say,  32-bit integer, you just work with "an
integer" and it could be a lot larger. For instance, you can take the
integer 1 and shift it by any number of places, thus getting any power
of two that you want:

>>> 1 << 10
1024
>>> 1 << 20
1048576
>>> 1 << 30
1073741824
>>> 1 << 5000
14124670321394260368352096670161473336688961751845411168136880858571181698427075125580891263167115263733560320843136608276420383806997933833597118572663992343105177785186539901187799964513170706937349821263132375255311121537284403595090053595486073341845340557556673680156558740546469964049905084969947235790090561757137661822821643421318152099155667712649865178220417406183093923917686134138329401824022583869272559614700514424328107527562949533909381319896673563360632969102384245412583588865687313398128724098000883807366822180426443291089403078902021944057819848826733976823887227990215742030724757051042384586887259673589180581872779643575301851808664135601285130254672682300925021832801825190734024544986318326563798786219851104636298546194958728111913990722800438594288095395881655456762529608691688577482893444994136241658867532694033256110366455698262220683447421981108187240492950348199137674037982599879141187980271758388549857511529947174346924111707023039810337861523279371029099265644
 
4842895511830355733152020804157920090041811951880456705515468349446182731742327685989277607620709525878318766488368348965015474997864119765441433356928012344111765735336393557879214937004347568208665958717764059293592887514292843557047089164876483116615691886203812997555690171892169733755224469032475078797830901321579940127337210694377283439922280274060798234786740434893458120198341101033812506720046609891160700284002100980452964039788704335302619337597862052192280371481132164147186514169090917191909376
>>>

Have fun!

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list

[OT] Bit twiddling homework

[Brian Oney via Python-list]

Dear Python-List,

an old dog wants to learn some new tricks.

Due to my contact with microcontrollers, I am learning C/C++. I am aware that 
this is the
endearing, helpful, yet chatty python-list. Many of you are competent 
C-programmers. 

The allure of C is that I can play directly with memory. 
For example, bitwise operators are neat (here a shift):
C:
  int res = 1 << 4 
  printf("%d\n", res)
16

Translates to pseudocrap:
 0001 -> leftwards bitshift of 4 places -> 0001 


I think that is pretty neat. After having imbibed the some of the computational 
basis for binary
digits (X₂) a few weeks ago, I learned yesterday about hexadecimals (X₁₆). 
While in the rabbit
hole, I learned about Claude Shannon's and Alan Turing's work on digital logic. 
I am excited to
learn about what kind of computations I can do in these number systems. 

Therefore, what book or learning course do you recommend? I imagine something 
that tours or skims
the fundamentals of Boolean algebra and digital logic, and then goes to C and 
some fun homework
problems. It may seem to you that the emphasis there is wrongly placed. 

Thank you for the tips.

Cheers,
Brian
PS: Can I twiddle bits in Python?
-- 
https://mail.python.org/mailman/listinfo/python-list