Re: [ANN] Lua 5.3.0 (work2) now available

[Tim Hill <drtimhill@...>]

On Mar 25, 2014, at 3:57 PM, Enrico Colombini <erix@erix.it> wrote:

> On 25/03/2014 21.05, Tim Hill wrote:
>> That said, for this project I cannot recall needing arithmetic shift,
>> just logical.
> 
> Probably because logical shifts are bitwise operations acting on bit arrays of defined length, assuming no intepretation of their meaning and therefore having many different applications where they cannot easily be replaced, while arithmetic shifts are just a shortcut for arithmetic operations on integer values coded in a specific way: two different beasts.
> 
> I don't use arithmetical shifts in C because thy are not guaranteed and because their meaning is, in fact, an integer division of a signed value by an unsigned power of two. I find it safer and clearer to write the latter.
> 
> Of course there may be particolr cases where one may want to operate on signed integer values at bit level, but they are much less common than generic bit manipulation or bit level operations on unsigned values.
> 
> -- 
>  Enrico
> 

No, this was just the nature of the problem at hand. Let’s be clear, arithmetic shift is a useful tool as a low-level operation for more than just shorthand division — this is the reason it exists as a basic operation in every mainstream CPU architecture. I’ve used it over the years for the signum function (where is works very well indeed) optimized bit-counting etc etc. It should be noted that almost all these uses are where performance is hyper-critical.

The issue here isn’t the general usefulness, it’s if arithmetic shift is useful in Lua in particular. And I can’t really see a need .. any very slight performance edge over division is going to be swallowed up in the overhead of the bytecode interpreter anyway.

As a side note, arithmetic shift is NOT equivalent to division by a power of two as the two functions have different rounding properties for negative dividends. Assuming you are using a C compiler that *does* do arithmetic shifts with signed operands, the following code will simulate integer division using shifts only:


////// divp2(): Fast divide by power of two (works for negative dividend)
// (fast version but assumes >> does an arithmetic shift)
// x			Value to divide (dividend/numerator)
// p			Power of two divisor (e.g. p=2 means x/4), must be positive
// returns		Result of (x / (2^p))
static inline int divp2(int x, int p) {
	int s = x >> ((sizeof(x) * 8) - 1);
	return (((x ^ s) - s) >> p) * (1 | s);
}

Yes, it’s ugly and complex, but was designed for very high performance on certain CPU architectures. OTOH it’s a good interview question to see if someone can figure out what the code does :)

—Tim