bit lib (was: [ANN] Lua 5.2.0 (work1) now available)

[Walter Luh <walterlua@...>]

Here are some examples from my own experience on embedded runtimes (formerly Flash Lite and now Corona) and graphics that might prove useful in this debate:

* In the book "Hacker's Delight", which I would assert as one of the authorities on bit manipulations (or bit machinations :) there are numerous uses of *both* logical and arithmetic right shifts.  I only offer this as a way for both sides to give context to their positions via examples.
* Our Corona developers are already using Lua-based bit libs (e.g. sudoku-solving algorithms) and are asking for better performance for bit libs.
* In graphics and image processing, pixel manipulations come to mind.

I'm forgetting a bunch, but (putting my diplomat hat on) I think if both sides started using real examples to illustrate their points, that would help the community greatly in understanding the final choices, especially if they could show concrete examples of what's possible, no longer possible, more difficult, slower, faster, etc.

And let's not forget that performance *is* a primary reason for having bit lib --- at least that's why I want it :)

Walter


On Jan 18, 2010, at 6:33 AM, Roberto Ierusalimschy wrote:

Roberto Ierusalimschy wrote:

Summary:
- Inputs to bit operations need to be converted in a consistent and
 platform-independent way, respecting modular arithmetic requirements.

We would like to do that. But we do not know a reasonable way to do it
in ANSI C89.

You can deal with it the same way you deal with popen(): make it
conditional, but enable it by default in this case (*).

The bit library needs to be made conditional, anyway: it should be
disabled for 32 bit floats, since the semantics just don't make
any sense there (loss of precision).

(*) Lua BitOp works on 16, 32 and 64 bit platforms with lua_Number
types IEEE 754 double, int32_t or int64_t. I've not found a single
OS/CPU/compiler combination that doesn't like it.

I am not worried about different number types or specific platforms.
Our "contract" is with doubles and ANSI. Although Lua provides some
optimizations for some arquitechtures, it always provides a fallback
case that should work with any ANSI compiler.

The bit library should not be conditional for this contract. So we need
an ANSI way to do that input.

[About the FP representation example: I've picked apart FP numbers
with bit operations in the past. But 1) it uses a biased exponent
and not a signed one and 2) there is no need for a bidirectional
shift. This use case rather asks for a masked shift count!]

We all did it. The biased exponent becomes a signed one as soon
as you subtract the bias. Except for the special cases (NaN, inf,
denormalized), the conversion is trivial with bidirectional shift
*and* shifting out all bits if exponent is too large/too small.

- Shift counts should be masked by the bit width.

Not convinced (see below).

You do not present any related arguments below.

It is the one about performance.

I repeat my arguments for masking the shift counts:
- It enforces defined behavior.

Shifting out also enforces defined behavior.

- It's based on actual needs of users.
- It simplifies a majority of actual use cases.

I still did not see the evidence.

- It works consistently for *all* shift or rotate instructions.

The same for shifting out. (rotate also does specify that it masks the
count: it just happens that rotate(x, 33) == rotate(x, 1).)

- It's consistent with the input conversions for other bit op
 arguments that respect the requirements of modular arithmetics.

??

When discussing language design, performance is always present. But
we do not think that, in a scripting language, such as Lua, we should
consider a change in an API just to avoid an extra conditional or a jump
misprediction.

This makes it sound as though a "scripting language" is some
inferior creature that doesn't deserve as much attention to its
design.

Maybe my English is not that clear, but I cannot see how what I said
could sound like "a 'scripting language' is some inferior creature that
doesn't deserve as much attention to its design."

And Lua is rarely used in the way that Perl or Bash is, so
the name is undeserved as well.

Lua *is* a scripting language.

If we use the "it's a scripting language, it can be slow" excuse
too often, we end up with Python. If we use the "it's a scripting
language, API design doesn't matter" excuse, we end up with PHP.
I sincerely hope I'll never see that day.

Again you are changing my words. This makes a discussion with you too
strenuous, which is sad. I did not say that "it can be slow".  What
I said is that Lua has a different time scale than C: One extra "if"
in a library function should not be considered a relevant cost if it
improves the API. And where on hell did I say that "API design doesn't
matter"?? I said (or tried to sell, again maybe my English is too poor)
exactly the opposite.

-- Roberto