Math.clz()

Jussi Kalliokoski jussi.kalliokoski at gmail.com
Mon Mar 5 09:57:03 PST 2012


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

On Mon, Mar 5, 2012 at 12:54 AM, Oliver Hunt <oliver at apple.com> wrote:

> 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.
>
> --Oliver
>
> On Mar 4, 2012, at 2:46 PM, Jussi Kalliokoski wrote:
>
> 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
>
>
>> --Oliver
>>
>>
>> On Mar 4, 2012, at 12:23 PM, Mark S. Miller wrote:
>>
>> 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 12: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.
>>>
>>>
>>> On Sun, Mar 4, 2012 at 1:38 AM, Jussi Kalliokoski <
>>> jussi.kalliokoski at gmail.com> wrote:
>>>
>>>> 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. :)
>>>>
>>>>
>>>> On Sun, Mar 4, 2012 at 10:01 AM, Tomas Carnecky <tomc at caurea.org>wrote:
>>>>
>>>>> 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.
>>>>>
>>>>> On Sat, 03 Mar 2012 23:21:11 -0800, Brendan Eich <brendan at mozilla.org>
>>>>> wrote:
>>>>> > I'm open to clz/clo. The names perhaps need to be less cryptic... or
>>>>> not.
>>>>> >
>>>>> > Allen should weigh in.
>>>>> >
>>>>> > /be
>>>>> >
>>>>> > Jussi Kalliokoski wrote:
>>>>> > > 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
>>>>> > >
>>>>> > > [1]: http://jsperf.com/read-leading-zeros/8
>>>>> > > [2]:
>>>>> http://wiki.ecmascript.org/doku.php?id=harmony:more_math_functions
>>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> es-discuss mailing list
>>>> es-discuss at mozilla.org
>>>> https://mail.mozilla.org/listinfo/es-discuss
>>>>
>>>>
>>>
>>>
>>> --
>>>     Cheers,
>>>     --MarkM
>>>
>>
>>
>>
>> --
>>     Cheers,
>>     --MarkM
>> _______________________________________________
>> es-discuss mailing list
>> es-discuss at mozilla.org
>> https://mail.mozilla.org/listinfo/es-discuss
>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20120305/6ba61202/attachment-0001.html>


More information about the es-discuss mailing list