Status

()

defect
RESOLVED FIXED
6 years ago
3 years ago

People

(Reporter: jrmuizel, Assigned: evilpie)

Tracking

(Blocks 1 bug, {dev-doc-complete, feature})

unspecified
mozilla31
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [DocArea=JS][qa-])

Attachments

(3 attachments)

Reporter

Description

6 years ago
This would be handy to have for emscriptened code.
Seems like it would.  Do you have a particular case in mind?
Reporter

Comment 2

6 years ago
(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.
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.
Yeah, I've found clz pretty useful before too.  Perhaps worth proposing Dave?
Flags: needinfo?(dherman)
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.
(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
(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.
(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.
OK - and I'm sorry for the harsh words.
Duplicate of this bug: 886944
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.
Flags: needinfo?(jorendorff)
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.
Brendan will put it on the agenda for the next TC39 face-to-face.
Flags: needinfo?(jorendorff)
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
Flags: needinfo?(dherman)
OS: Mac OS X → All
Hardware: x86 → All
Summary: Add Math.clz builtin → Add Math.clz32 builtin
Keywords: feature
Whiteboard: [DocArea=JS]
Assignee

Updated

5 years ago
Assignee: nobody → evilpies
Assignee

Comment 15

5 years ago
Posted patch clz32Splinter Review
Attachment #8404189 - Flags: review?(jwalden+bmo)
Assignee

Comment 16

5 years ago
Posted patch wipSplinter Review
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.
Assignee

Updated

5 years ago
Attachment #8404189 - Flags: review?(jwalden+bmo) → review?(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.
Attachment #8404189 - Flags: review?(till) → review+
Assignee

Updated

5 years ago
Blocks: 995230
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
https://hg.mozilla.org/mozilla-central/rev/0defba733d7d
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
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.
Whiteboard: [DocArea=JS] → [DocArea=JS][qa-]
(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.
Adds in clz support for ARM.
Attachment #8407402 - Flags: review?(Jacob.Bramley)
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.
Attachment #8407402 - Flags: review?(Jacob.Bramley) → review-
Assignee

Comment 27

5 years ago
I actually opened bug 995230 for jit support.

Comment 29

4 years ago

> > 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)` ?
You need to log in before you can comment on or make changes to this bug.