Re: [Jprogramming] A bit-twisting puzzle

Note that the very hard-to-fix Spectre exploit is named after the "Speculative execution" that we are talking about here. On Mon, Jul 29, 2019 at 2:14 PM Roger Hui wrote: > A relevant quote, the final sentence in *Notation as a Tool of Thought > *: > > Fi

Re: [Jprogramming] A bit-twisting puzzle

A relevant quote, the final sentence in *Notation as a Tool of Thought *: Finally, overemphasis of efficiency leads to an unfortunate circularity in design: for reasons of efficiency early programming languages reflected the characteristics of the early com

Re: [Jprogramming] A bit-twisting puzzle

From: Programming On Behalf Of Don Guinn Sent: Monday, July 29, 2019 11:04 AM To: Programming forum Subject: Re: [Jprogramming] A bit-twisting puzzle Yes. IBM's going ahead and executing both legs of the conditional branch has always bothered me too. But I guess math units were relativel

Re: [Jprogramming] A bit-twisting puzzle

it. Linda -Original Message- From: Programming On Behalf Of Don Guinn Sent: Monday, July 29, 2019 11:04 AM To: Programming forum Subject: Re: [Jprogramming] A bit-twisting puzzle Yes. IBM's going ahead and executing both legs of the conditional branch has always bothered me t

Re: [Jprogramming] A bit-twisting puzzle

Yes. IBM's going ahead and executing both legs of the conditional branch has always bothered me too. But I guess math units were relatively cheap and it presented a novel way to speed up conditional branches. Shades of quantum computing. My comment about destroying a was that a was not copied, but

Re: [Jprogramming] A bit-twisting puzzle

Yes, that's a problem.  You have to have some datasets that you consider typical.  I usually try on random, ascending/descending, and somewhat repeated data. In this case, where the performance depends on the instruction mix in user code, I just guess based on the J code I have written. Henr

Re: [Jprogramming] A bit-twisting puzzle

Your instruction timings are right, but I question whether two branches would be better if the each input is zero, say, half the time randomly. a+b == (a>b?a:b) is a good trick! The fact that or doesn't fuse and cmp does is important.  It means that a+b == (a>b?a:b) takes only 4 microops, same

Re: [Jprogramming] A bit-twisting puzzle

MPA,B BZ STMT From: Programming on behalf of Henry Rich Sent: Monday, July 29, 2019 1:51:34 AM To: programm...@jsoftware.com Subject: [Jprogramming] A bit-twisting puzzle Many of the members of this Forum will remember the days of

Re: [Jprogramming] A bit-twisting puzzle

Henry MP A,B Multiply & set CC BZ STMT STMT EQU * From: Programming on behalf of Roger Hui Sent: Monday, July 29, 2019 5:49:28 AM To: programm...@jsoftware.com Subject: Re: [Jprogramming] A bit-twisting puzzle If you have tho

Re: [Jprogramming] A bit-twisting puzzle

Which reminds me of an interesting question: How do you adequately benchmark this kind of optimization? Thanks, -- Raul On Mon, Jul 29, 2019 at 8:42 AM Henry Rich wrote: > > That's a good solution, same idea as Gilles's. As for OR destroying a > register, nowadays all registers are virtual a

Re: [Jprogramming] A bit-twisting puzzle

Two instructions but one of them's slow. I found the test a+b == (a>b?a:b) on unsigned integers to be slightly faster in a loop with independent iterations and significantly faster when a loop dependency is introduced. However, a solution with two branches was usually faster than either. I loaded

Re: [Jprogramming] A bit-twisting puzzle

That's a good solution, same idea as Gilles's.  As for OR destroying a register, nowadays all registers are virtual anyway. Intel machines have 150-odd registers in the execution unit IIRC, even though the programming model presents only 16 to the programmer.  Copying a register doesn't even ta

Re: [Jprogramming] A bit-twisting puzzle

First. Since you referred to BXLE I assume you are talking IBM 370 or beyond architecture. Unfortunately, I don't know INTEL instructions, but your example implies that maybe you are thinking INTEL. I have a problem with your use of "or" as wouldn't that destroy the contents of a? And several peop

Re: [Jprogramming] A bit-twisting puzzle

: programm...@jsoftware.com Subject: [Jprogramming] A bit-twisting puzzle Many of the members of this Forum will remember the days of assembler language   ...and who could less than merry be   when writing out BXLE? AND, OR, XOR were our meat.  Those days are returning. You have two integer variabl

Re: [Jprogramming] A bit-twisting puzzle

I'm glad I posted this to the Forum, because I had been thinking in terms of standard C, and not about extensions. The best so far is Gilles's idea, assuming you can get to the entire product:    take a*b; if((high_product|low_product)==0)stmt; 2 instructions+1 branch.  Gonna be hard to beat

Re: [Jprogramming] A bit-twisting puzzle

are.com Subject: [Jprogramming] A bit-twisting puzzle Many of the members of this Forum will remember the days of assembler language   ...and who could less than merry be   when writing out BXLE?AND, OR, XOR were our meat.  Those days are returning.You have two integer variables a and b and you want to

Re: [Jprogramming] A bit-twisting puzzle

:51 PM (GMT-05:00) To: programm...@jsoftware.com Subject: [Jprogramming] A bit-twisting puzzle Many of the members of this Forum will remember the days of assembler language   ...and who could less than merry be   when writing out BXLE?AND, OR, XOR were our meat.  Those days are returning.You h

Re: [Jprogramming] A bit-twisting puzzle

Yes, POPCNT can be used this way.  It's not what I was thinking of, but you have solved the problem. (POPCNT(~a)|POPCNT(~b)) >> 6    (on 64-bit machines) works. (a*b)==0 fails because the product may overflow, leaving the lower part 0. Can you improve on your 6-instruction solution? Henry

Re: [Jprogramming] A bit-twisting puzzle

I think of a nand-function. On 29-07-19 02:51, Henry Rich wrote: Many of the members of this Forum will remember the days of assembler language   ...and who could less than merry be   when writing out BXLE? AND, OR, XOR were our meat.  Those days are returning. You have two integer variables

Re: [Jprogramming] A bit-twisting puzzle

I am missing something: a == 0 iff popcnt(a) == 0, so indeed a == 0 || b == 0 is equivalent to popcnt(a) == 0 || popcnt(b) == 0 which can be written as !(popcnt(a) && popcnt(b)), but if this is translated into a single-branch sequence of machine instructions, then wouldn’t !(a && b) be as well? T

Re: [Jprogramming] A bit-twisting puzzle

If you have thought about this for a year then the following can't be the answer, but here it is: There is either a popcnt instruction, or you can implement it with straight-line code without branching. Whence: if !(popcnt(a)&&popcnt(b)) stmt; On Sun, Jul 28, 2019 at 5:51 PM Henry Rich wrote:

Re: [Jprogramming] A bit-twisting puzzle

How about multiply a and b, followed by a branch on zero? ~ Gilles Le 2019-07-28 à 20:51, Henry Rich a écrit : > Many of the members of this Forum will remember the days of assembler > language > >   ...and who could less than merry be >   when writing out BXLE? > > AND, OR, XOR were our meat.  T

Re: [Jprogramming] A bit-twisting puzzle

Do we have access to an instruction which counts leading zero bits? Interesting problem, Louis > On 28 Jul 2019, at 19:51, Henry Rich wrote: > > Many of the members of this Forum will remember the days of assembler language > > ...and who could less than merry be > when writing out BXLE? >

[Jprogramming] A bit-twisting puzzle

Many of the members of this Forum will remember the days of assembler language   ...and who could less than merry be   when writing out BXLE? AND, OR, XOR were our meat.  Those days are returning. You have two integer variables a and b and you want to do something if one or both of them are 0