925123 - Add Math.clz32 builtin

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jeff Muizelaar [:jrmuizel]]

This would be handy to have for emscriptened code.

Comment 1

[Luke Wagner [:luke]]

Seems like it would.  Do you have a particular case in mind?

Comment 2

[Jeff Muizelaar [:jrmuizel]]

(In reply to Luke Wagner [:luke] from comment #1)
> Seems like it would.  Do you have a particular case in mind?

It's used in https://github.com/jrmuizel/full-scene-rasterizer for determining the log2 of the number of segments to divide curves into. 

Some other info: __builtin_clz() has an undefined result for 0. I expect this is because the bsr instruction x86 has this property. We wouldn't want the undefined behaviour and should have clz() return 32 for 0. x86 has this fixed with the lzcnt instruction and the defined behaviour is easy to implement on top of bsr.

Comment 3

[Marty Rosenberg [:mjrosenb]]

This is also easy to implement as either one or two instructions on arm.  I am all in favor.  IIRC, the default allocator that is used with emscripten has a godawful built in implementation that it falls back to.

Comment 4

[Luke Wagner [:luke]]

Yeah, I've found clz pretty useful before too.  Perhaps worth proposing Dave?

Comment 5

[Jason Orendorff [:jorendorff]]

This is already in the draft spec, it's called Number.prototype.clz.
  http://people.mozilla.org/~jorendorff/es6-draft.html#sec-number.prototype.clz
  (There's bug 886944 but nothing much to see there yet.)

The rationale for this weird decision is here (search for clz in the page):
  http://esdiscuss.org/notes/2013-07-25

I wonder if we might reverse this, for users' sake. The pattern in ES1-5 is fairly strong; math functions generally go on the Math object. The only exception... no, wait, there aren't any exceptions.

It could be called Math.clz32() to address concerns about future 64-bit integer types.

Comment 6

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Jason Orendorff [:jorendorff] from comment #5)
> I wonder if we might reverse this, for users' sake. The pattern in ES1-5 is
> fairly strong; math functions generally go on the Math object. The only
> exception... no, wait, there aren't any exceptions.
> 
> It could be called Math.clz32() to address concerns about future 64-bit
> integer types.

If it's in Math, it might need a supplementary step to return NaN if there's no input.

What would be a nice implementation in the interpreter? Wikipedia's one only uses bitwise operations [0], but there might be something "easier" like clz(x) == 31 - floor(log2(x)), if x !== 0.

For the JITs, lzcnt is apparently SSE4 specific, so applying bsr and the subtract might be easier.

[0] https://en.wikipedia.org/wiki/Count_leading_zeros

Comment 7

[Jason Orendorff [:jorendorff]]

(In reply to Benjamin Bouvier [:bbouvier] from comment #6)
> If it's in Math, it might need a supplementary step to return NaN if there's
> no input.

I can't tell how seriously you think I should take this. There's no need to play devil's advocate unless there is an actual argument against that you'd like to explore. We both have better things to do than knock down straw men.

The spec for Math.clz32() would look a lot like Math.imul():
http://people.mozilla.org/~jorendorff/es6-draft.html#sec-math.imul

It's not super long.

> What would be a nice implementation in the interpreter? Wikipedia's one only
> uses bitwise operations [0], but there might be something "easier" like
> clz(x) == 31 - floor(log2(x)), if x !== 0.

I'm not aware of any trick for this. I'm not confident that we can depend on log2 having the necessary properties on all platforms to rely on it here.

Comment 8

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Jason Orendorff [:jorendorff] from comment #7)
> 
> I can't tell how seriously you think I should take this. There's no need to
> play devil's advocate unless there is an actual argument against that you'd
> like to explore. We both have better things to do than knock down straw men.

Oops. Take this more as a naive-spec-reader-beginner remark I made than a concrete argument. I wasn't arguing in favor of anything, just thought about that as an implementation step, as I was interested in doing it, but never mind. Sorry for the noise.

Comment 9

[Jason Orendorff [:jorendorff]]

OK - and I'm sorry for the harsh words.

Comment 11

[Till Schneidereit [:till]]

Jason, do you think we should try reverting the naming decision, as you proposed in comment 5? It might be too late for that now, I'm afraid.

Comment 12

[Jeff Walden [:Waldo]]

I think pushing back a little on the naming decision is worth trying.  It's just a standard decision, not a shipped thing, so why would it be too late to try renaming it?  A couple few days of mailing list pushback seems low-cost, no reason at all not to attempt/try.

Tho if it comes to it, having Math.clz and Math.clz64 doesn't seem like the end of the world to me -- just the sort of thing that's likely to confuse people in practice.  A language wart, but a small one.

I can't remember if I mentioned it anywhere, but "clz" seems uncharacteristically terse for a JS function/method name.  Even for the Math.* naming conventions.  I don't have any good ideas that fit that narrow name-set's conventions while being clearer.  Just noting in case anyone else has bright ideas.

Comment 13

[Jason Orendorff [:jorendorff]]

Brendan will put it on the agenda for the next TC39 face-to-face.

Comment 14

[Till Schneidereit [:till]]

Brendan posted to es-discuss[1]:
"Thanks, I just presented this pretty much verbatim, and Math.clz32 it is, by TC39 consensus. ToUint32 on parameter, 0 => 32 and all."

[1]: http://esdiscuss.org/topic/rename-number-prototype-clz-to-math-clz#content-36

Comment 15

[Tom S [:evilpie]]

Attachment: clz32

Comment 16

[Tom S [:evilpie]]

Attachment: wip

Wow Mir.h got really complicated. I think we might want to add some optimization that allows use to not emit the zero check. I haven't done ARM.

Comment 17

[Till Schneidereit [:till]]

Comment on attachment 8404189 [details] [diff] [review]
clz32

Review of attachment 8404189 [details] [diff] [review]:
-----------------------------------------------------------------

Nice!

I know that you already started on that, but it'd be really nice to have the inlined version of this land soon, too. Not only is jorendorff right in saying that implementing features without optimizing them, too, is not much better than not implementing them at all - clz seems particularly pointless if it's dog-slow.

::: js/src/tests/ecma_6/Math/clz32.js
@@ +1,3 @@
> +// Undefined and NaN end up as zero after ToUint32
> +assertEq(Math.clz32(), 32);
> +assertEq(Math.clz32(NaN), 32);

Can you add tests for null, false, true, fractional number, object, empty and non-empty array, and empty and non-empty string, too? I know that the right thing will happen, but it'd be nice for this to be a bit more exhaustive.

Comment 18

[Tom S [:evilpie]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e8dfde56e9ca

Comment 19

[Ed Morley [:emorley]]

Backed out for:
https://tbpl.mozilla.org/php/getParsedLog.php?id=37634656&tree=Mozilla-Inbound
REFTEST TEST-UNEXPECTED-FAIL | file:///builds/slave/talos-slave/test/build/tests/jsreftest/tests/jsreftest.html?test=ecma_6/Math/clz32.js | No test results reported. (SCRIPT)


https://hg.mozilla.org/integration/mozilla-inbound/rev/d0bce5d9c518

Comment 20

[Tom S [:evilpie]]

I forgot to call reportCompare.
https://hg.mozilla.org/integration/mozilla-inbound/rev/0defba733d7d

Comment 21

[ziyunfei]

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32

Comment 22

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/0defba733d7d

Comment 23

[u279076]

I'm not sure this is something QA needs to take a look at. If there's potential for regression here please help me in identifying areas we may want to do some focused testing. Thanks.

Comment 24

[Till Schneidereit [:till]]

(In reply to Anthony Hughes, QA Mentor (:ashughes) from comment #23)
> I'm not sure this is something QA needs to take a look at.

It's not: this is covered by automatic tests.

Comment 25

[Marty Rosenberg [:mjrosenb]]

Attachment: add_clz-r0.patch

Adds in clz support for ARM.

Comment 26

[Jacob Bramley [:jbramley]]

Comment on attachment 8407402 [details] [diff] [review]
add_clz-r0.patch

Review of attachment 8407402 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/arm/Assembler-arm.cpp
@@ +1532,5 @@
>      return writeInst(0x0730f010 | c | RN(rd) | RM(rm) | rn.code());
>  }
>  
> +BufferOffset
> +Assembler::as_clz(Register rd, Register rm, Condition c,uint32_t *dest)

You haven't used rd, so the encoded instruction cannot be correct.

There's a missing space before `uint32_t *dest`.

@@ +1534,5 @@
>  
> +BufferOffset
> +Assembler::as_clz(Register rd, Register rm, Condition c,uint32_t *dest)
> +{
> +    return writeInst(IsData | IsMisc | IsCLZ | c | rm.code() | RM(pc) | RN(pc),dest);

I don't like the IsData/IsMisc mechanism here. They're hard to validate against the presentation in the ARM ARM, and there are probably exceptions which don't fit the pattern. Similarly, I don't like the use of 'RN(pc)' to encode 0x000f0000. It is semantically incorrect, and it isn't obvious what the resulting encoding would be.

Following the trend set in the other instructions would be best, I think:

// Rm is encoded at offset 0, not at the standard RM() location.
writeInst(0x016f0f10 | c | RD(rd) | rm.code(), dest);

::: js/src/jit/arm/Assembler-arm.h
@@ +341,5 @@
> +// bits 4, 25, 26, and 27 together identify the 'kind' of instruction
> +enum InstTag {
> +    IsData       = 0 << 25 | 0 << 4,
> +    IsLoadStore  = 2 << 25 | 0 << 4,  // Uses bit 25 to determine Immediate or Register
> +    IsMedia      = 3 << 25 | 1 << 4,  // massive overlay with LoadStore.  

Trailing whitespace.

Comment 27

[Tom S [:evilpie]]

I actually opened bug 995230 for jit support.

Comment 28

[Florian Scholz (Open Web Docs)]

New page 
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32

Added to
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math
https://developer.mozilla.org/en-US/Firefox/Releases/31#JavaScript

Thanks to ziyunfei and evilpie.

Comment 29

[4esn0k]

> > What would be a nice implementation in the interpreter? Wikipedia's one only
> > uses bitwise operations [0], but there might be something "easier" like
> > clz(x) == 31 - floor(log2(x)), if x !== 0.


> I'm not aware of any trick for this. I'm not confident that we can depend on log2 having the necessary > properties on all platforms to rely on it here.


What about `31 - (Math.log2(value + 0.5) | 0)` ?

Comment 30

[sf2164229838]

bug 1322951