Math.clz()
I'm open to clz/clo. The names perhaps need to be less cryptic... or not.
Allen should weigh in.
Wouldn't it be better to namespace these bit-operators in a different module? Bit.clz() perhaps? The Math module is getting a bit crowded.
Bit.clz() sounds just as good to me. I don't know if they need to be less cryptic, if someone doesn't know the abbreviation, it is highly likely (s)he doesn't need the functions either. :)
Maybe make it generic? Although that might not be very important for the case of counting leading zeroes or ones.
I'd love a function for getting n consecutive bits (to left or right..) from number x starting from the nth bith (from the left or right) as a single number as if the lsb was 1. You can create masks for this to & and >>, but it's not as versatile. Also, maybe a
toString function for binary with leading zero padding (or are we getting String#pad now?).
I'm not sure I understood correctly, but... I think for the sake of this being a useful performance optimization, it shouldn't have any overloads / optional arguments, maybe a separate function for that is a better.
Also, while we are adding things to the Bit namespace, I'm not sure if ctz/cto (count trailing zeroes/ones) are really useful, I've never figured out a use case for them, but while at it, why not add it, might be useful in the future, although I highly doubt it.
As for the string padding, it might be a bit redundant, but I don't know.
Can we really add a "Bit" namespace without breaking the web? Maybe "Math.Bit" if we really want a bitwise operation namespace?
clz, clo, the names are cryptic but so are their applications -- so I think it's a good fit. zLen and oLen might also make good names.
These could be handy for other things, too, provided they work on at least 32-bit numbers. They would need coercion rules similar to what << and >>
have right now. And, what does clz(0) yield? 53?
An interesting "overload" might be letting them work on typed arrays, too.
I agree that there are useful functions when doing bit level decoding. Luke has been championing the Math function additions for ES.next so he should probably be the one to look at these specifically.
I assume that this function would apply ToInt32 to its argument. In other words, it is analyzing a 32-bit two's complement value.
Is there are precedent from other languages or numeric libraries for these particular names or the specific form of the result.
I've seem machine level instruction sets that have a FFO (Find First One) instruction that return the bit position of the first 1 bit (starting form the high-order end). If you know the word length it is easy to transform FFO into FFZ or CLZ/CLO. For the common use cases is there any particular algorithmic advantage to bit counts vs. bit positions?
On Sun, Mar 4, 2012 at 4:45 PM, Wes Garland <wes at page.ca> wrote:
Can we really add a "Bit" namespace without breaking the web? Maybe "Math.Bit" if we really want a bitwise operation namespace?
clz, clo, the names are cryptic but so are their applications -- so I think it's a good fit. zLen and oLen might also make good names.
zLen/oLen might be a bit ambiguous, especially if trailing zero/one calculation is added as well.
These could be handy for other things, too, provided they work on at least 32-bit numbers. They would need coercion rules similar to what << and >> have right now. And, what does clz(0) yield? 53?
Since JS bitwise operations work as 32-bit integers clz(0) === 32 && clz(-1) = 0. Yeah, coercion rules should be applied.
An interesting "overload" might be letting them work on typed arrays, too.
I thought this would be too much to ask, but that would be really useful. But that's a whole another discussion actually, because imho it would be an extremely useful optimization if all Math functions could be applied on typed arrays for vector-like usage. But I'm not sure if those things belong in Math/Bit namespaces, as overloads contribute to making it harder to optimize these functions that have high performance requirements. Instead, extending the typed arrays with helper functions such as these might be a better idea, like this:
new Int32Array([~0xFFFFFFFF, ~~0xFFFFFFFF]).clz(); // {0: 32, 1: 0} new Float32Array([0.0, 0.1, 0.2, 0.3]).sin(); // Houston, we have an oscillator. new Uint8Array([0, 1, 2, 4]).pow(2); // {0: 0, 1: 1, 2: 4, 3: 16}
To further make these useful performance optimizations (see, I keep saying that, but it kind of matters in what we do), they wouldn't create new arrays, but instead the resulting values would be stored in the original array. This might be a bit confusing, but if you needed to create a new array, you'd just have to be a bit explicit:
var a = new Uint8Array([0, 1, 2, 4]); var b = new Uint8Array(a.length); b.set(a); b.pow(2);
It would be sad if you'd have to create a new array every time you just wanted to run these algorithms on the array.
However, since with vectors/arrays, setup costs apply already, I think these can be safely overloaded, for example:
new Uint8Array([0, 1, 2, 3]).multiply(2); // {0: 0, 1: 2, 2: 4, 3: 6} new Uint8Array([0, 1, 2, 3]).multiply(new Uint8Array([3, 2, 1, 0])); // {0: 0, 1: 2, 2: 2, 3: 0}
Maybe even this, if we want to go crazy:
myFloat32Array.fft(); myFloat32Array.ifft(); myFloat32Array.rfft(); myFloat32Array.irfft();
Imagining the new JavaScript, eh?
On Sun, Mar 4, 2012 at 6:44 PM, Allen Wirfs-Brock <allen at wirfs-brock.com>wrote:
I agree that there are useful functions when doing bit level decoding. Luke has been championing the Math function additions for ES.next so he should probably be the one to look at these specifically.
I assume that this function would apply ToInt32 to its argument. In other words, it is analyzing a 32-bit two's complement value.
Yes.
Is there are precedent from other languages or numeric libraries for these particular names or the specific form of the result.
I've seem machine level instruction sets that have a FFO (Find First One) instruction that return the bit position of the first 1 bit (starting form the high-order end). If you know the word length it is easy to transform FFO into FFZ or CLZ/CLO. For the common use cases is there any particular algorithmic advantage to bit counts vs. bit positions?
Nowadays, clz is the most common of these as an instruction [1], mainly because the rest are fastest calculated from that.
Jussi
It seems very strange to me to have a "clz" and "getOwnPropertyDescriptor" coexist as naming choices in the same language. I have taken to doing
var gopd = Object.getOwnPropertyDescriptor;
early in many of my source files. I think this is better than standardizing an obscure acronym. This way, for every file that "clz" or "gopd" appears in, there's a declaration at the beginning stating the correspondence with a name whose meaning is easier to guess. This practice becomes even better supported by our new module system's import-with-renaming.
Let's keep exported names clear. Let's abbreviate if necessary on import.
Please don't take my message as an endorsement that these operations should be standardized at all, under any name. I do not yet have an opinion about that.
On Sun, Mar 4, 2012 at 10:22 PM, Mark S. Miller <erights at google.com> wrote:
It seems very strange to me to have a "clz" and "getOwnPropertyDescriptor" coexist as naming choices in the same language. I have taken to doing
var gopd = Object.getOwnPropertyDescriptor;early in many of my source files. I think this is better than standardizing an obscure acronym. This way, for every file that "clz" or "gopd" appears in, there's a declaration at the beginning stating the correspondence with a name whose meaning is easier to guess. This practice becomes even better supported by our new module system's import-with-renaming.
Let's keep exported names clear. Let's abbreviate if necessary on import.
I sort of agree with this, although the JS1K devil in me is trying to fight it.
It's worth noting that even "high performance" languages like C don't have clz, etc builtin - people still have to drop down to assembly to implement them. If you really wanted to you could just use the standard bit fiddling techniques, and if necessary JS engines would start optimising those specific patterns (I say this based on the various other inane things that we've all optimised over time sigh)
On Sun, Mar 4, 2012 at 11:50 PM, Oliver Hunt <oliver at apple.com> wrote:
It's worth noting that even "high performance" languages like C don't have clz, etc builtin - people still have to drop down to assembly to implement them. If you really wanted to you could just use the standard bit fiddling techniques, and if necessary JS engines would start optimising those specific patterns (I say this based on the various other inane things that we've all optimised over time sigh)
But you can't really drop down to assembly from JS, and high performance "languages" like most used variations of assembly have it. :) And just because other languages don't have a useful feature, it doesn't mean that JS shouldn't have it. And we currently are using standard bit fiddling techniques, see the OP, and the performance is a bit poor for now. I also imagine it would be far easier for engine providers to optimize a function with a specific purpose that has an equivalent processor instruction than a crazy pattern that might just be clz.
Jussi
Make test cases where the bit-fiddly technique is too slow and file bugs on the various bug trackers: bugs.mozilla.org, bugs.webkit.org and somewhere on chromium.org :D
It's possible (given the relative infrequency of bitops) that most engines are still doing stuff that's really dumb -- i know JSC still has plenty of low-hanging fruit (I'd be kind of surprised if computing clz was the actual hot point in any engine), hence the need for real testcases -- simply performing bit ops in a loop is not necessarily useful as a test case because the surrounding code may be causing breakages.
That said if we did end up pulling clz and related instructions into the language, I think I'd much rather have it be after we've got modules fully spec'd and can start simply defining modules that should be available by default.
The performance isn't actually even the main point, it's also about the fact that JS is more and more used for binary operations, such as our codecs, bit counting methods make using the language more expressive, and for example OpenCL, CUDA, GCC, Clang and Posix libc have them mainly for that reason.
I don't really have an opinion of where in the language it goes, a module, namespace, whatever, as long as it's there. :)
And as for filing the bugs, I'm a bit hesitant to do that since different versions seem to perform quite differently between JS engines, so if you'd want to go optimizing a pattern, first you'd have to decide which of them is the best and should be optimized. I'd prefer none, because they're all pretty ugly hacks. Maybe the most expressive and intent-clear pattern is the clz(x) -> 32 - x.toString(2).length, but it isn't currently very fast.
Jussi
We're working on JS audio decoders, and one huge performance issue atm is clz() [count leading zeroes], which is a very commonly used algorithm in decoders. We've tried several different approaches and benchmarked them 1, however, different approaches work better on different engines, so optimizing the function is a bit of a no-go, especially if we want to have it fast in the future as well.
So, I thought I'd propose something that would go well with the earlier proposals to extend Math 2:
Math.clz(number)
This would allow for great speed boost in our decoders if it the JS engine had this built-in and optimized.
While at it, it might be wise to add other related functions as well, such as clo (count leading ones), although not as useful.
Cheers, Jussi