Repository navigation
Description
See constant(start, end, step, type) at https://www.w3.org/TR/webnn/#dom-mlgraphbuilder-constant-start-end-step-type
Problem
Computing the output shape indirectly from a floating-point calculation is brittle because the caller, depending on its equation and rounding, can yield a different size from WebNN which will cause graph execution to fail due to mismatched tensors. Such incompatible off-by-one differences can occur via differing calculation precisions (e.g. the caller computes the output shape in float64 whereas Chromium computes it in float32) and via differing handling of the inclusive/exclusive end value (see a non-hypothetical example below). So it's prudent for the library to pass WebNN the shape explicitly, and we've increasingly been moving toward more explicitness anyway (e.g. removing the special null values in Reshape). The output shape was in the fillSequence operator, but got dropped, and it reoccurred to me while reviewing Bin's Chromium implementation.
Proposal
- constant(start, end, step, type) method steps are:
+ constant(start, step, outputShape, type) method steps are:
...
- Let size be max(0, ceil((end - start)/step)).
- Set descriptor.[dimensions](https://www.w3.org/TR/webnn/#dom-mloperanddescriptor-dimensions) to [size].
+ Set descriptor.[dimensions](https://www.w3.org/TR/webnn/#dom-mloperanddescriptor-dimensions) to [outputShape].
+ Let outputElementCount be the product of all elements in descriptor.[dimensions](https://www.w3.org/TR/webnn/#dom-mloperanddescriptor-dimensions).
...
- [For each](https://infra.spec.whatwg.org/#map-iterate) index in [the range](https://infra.spec.whatwg.org/#the-range) 0 to size, exclusive:
+ [For each](https://infra.spec.whatwg.org/#map-iterate) index in [the range](https://infra.spec.whatwg.org/#the-range) 0 to outputElementCount, exclusive:* Note the end is now redundant, since it was only used for size calculation, not needed for the core start + (index * step) formula.
Problematic Library differences
We see differences between TF and PT with the exact same inputs due to how they handle the end result (included vs excluded), which emphasizes why WebNN should be clearly informed by the caller of the expected shape:
import tensorflow
result = tensorflow.range(5, 5, 2)
print("value:", result)
# output = [], shape= (0,)import torch
result = torch.range(5, 5, 2)
print("value:", result)
# output = [5], shape= (1,)Usage Examples
... = constant(0, 1, [3,3], "float32"); // Fill with an increasing sequence.
// output = [[0,1,2],[3,4,5],[6,7,8]
... = constant(9, -1, [3,3], "float32"); // Fill with a decreasing sequence.
// output = [[9,8,7],[6,5,4],[3,2,1]
... = constant(1, 0, [3,3], "float16"); // Quickly fill large tensor with a constant value, like numpy.ones(outputShape).
// output = [[1,1,1],[1,1,1],[1,1,1] // Note this is currently awkward otherwise for float16, because you have to
// pass 0x3C00 (1.0) to fill a Uint16Array.
Activity
[-]Constant sequential filling operation needs shape parameter[/-][+]Constant sequential filling operation needs output shape parameter[/+]huningxin commentedon Jan 2, 2024
Could the parameters
outputShapeandtypebe encapsulated byMLOperandDescriptor?miaobin commentedon Jan 10, 2024
So the final proposal is like this: constant(start, step, operand_descriptor), right (I guess the order of parameters is like this)? @huningxin @fdwr WDYT?
fdwr commentedon Jan 10, 2024
I'm fine with it either way. If you as a caller already have shape and data type variables, then requiring a temporary tensor desc is a little more bothersome than just passing them directly as parameters, but if you already have a tensor desc, then passing that directly is slightly more convenient. 🤷♂️ Since the internal implementation complexity doesn't really change either way, maybe asking someone from the WebNN API caller point of view (like Wanming from ORT) would be a nice tie breaker?
Whatever we do, we should use the same pattern in the future with similar operators. So if we introduce, for example, a diagonal matrix operator that fills a new tensor with 1's along the diagonal and 0's everywhere else, then it should take a tensordesc or two separate parameters. I don't see that we have much existing precedent though. Any ops that take a shape currently (like reshape or expand) take the shape as a separate parameter, and ops that take a data type take them as a separate parameter (like cast), but we don't have any others that take both shape and data type.
Honry commentedon Jan 10, 2024
No much impact to WebNN EP, I am fine with it either way as well.
zolkis commentedon Jan 10, 2024
In Web APIs they usually prefer passing options in dictionaries.
Semantically important parameters make sense to be passed as args, if there is not many of them.
fdwr commentedon Jan 10, 2024
Well these are essential parameters, not options, but it would be more consistent with the existing
constant(descriptor, bufferView)overload to accept a tensor descriptionMLOperandDescriptor. So, seeing that precedent, I more clearly favor making it takeMLOperandDescriptortoo. Then we would have these two (or three) overloads:Usage:
If it causes no ambiguity in the IDL, then I'd like both overload parameters to go in the same order, rather than inconsistently reversed between them. Also if you make
stepoptional (defaulting to 0), then that satisfies the reasonably likely use case of wanting to fill with a solid value (const y = builder.constant({dataType: 'uint32', dimensions: [4]}, 1.0)). Conveniently, I think that also obviates theconstant(value, type)overload?wacky6 commentedon Jan 11, 2024
I think marking fields are
requiredin IDL dictionary is fine (it's not uncommon). So the proposal in #492 (comment) looks reasonable to me.The following is also fine IMO.
dictionary FillSequenceDescriptor { required double start; double step = 0; }; constant(MLOperandDescriptor desc, FillSequenceDescriptor fillSequence);The type we use for
startandstepmight be tricky. I think we'll at least need adoubleto cover int32 and float32 (fp32 can't accurately represent large int32startvalue).How to support for int64 remains an open question :)
fdwr commentedon Jan 12, 2024
One of the three current
constantoverloads already takes adouble...MLOperand constant(double value, optional MLOperandDataType type = "float32");...and so there's precedent for passing at least that much precision. I agree that float32 is not sufficient to cover the accuracy needed (it cannot even represent odd int32 values >= 16777216 accurately).
One operator (split) already accepts parameters of differing types:
So (barring any IDL issues I'm not seeing?) we could accept
(double or BigInt)to accurately cover the full floating point and integer range:Curiously I see a
BigUint64Array, but I don't see a matchingBigUinttype? 🙃 I suppose it doesn't matter because a BigInt can hold unsigned values too, with the precise typeuint64being clarified by the operand desc's dataType (and I see thatBigInt.asUintN(64, (2n ** 64n) - 1n)runs fine, printing 18446744073709551615n as expected).miaobin commentedon Jan 12, 2024
I thought of the same method as you. And I am trying to add bigint to verify the feasibility of the implementation.
miaobin commentedon Feb 5, 2024
Updates to the constant sequential filling operation:
CL5091540 (extends the build method of constant) and CL5243778 (defines mojom and DirectML node) are developed according to IDL:
MLOperand constant(MLOperandDescriptor desc, (double or bigint) start, (double or bigint) step);We met the problem of using the keyword
orin IDL to create a union type containing double and bigint. In the generated file "v8_union_bigint_double.cc", it was only judged that the incoming data was of JS number type and there is no judgment that it is BigInt, which causes an error to be reported when BigInt data is passed in when calling this API using JS code. (For example, when we call constant op, we pass instart=123n). @fdwr Maybe we should file an issue to chromium for this problem?On one hand, we can continue to review these two CLs to find potential problems and verify feasibility. On the other hand, can we first create an updated specification PR which matches what is being implemented and get folks with more WebIDL and JavaScript API design knowledge to take a look at it to make sure it will work the way we intend it to as Reilly said? WDYT @huningxin @fdwr @wacky6
inexorabletash commentedon Feb 17, 2024
Drive-by comment: Use of bigint is extremely limited in Chromium at the moment, so I'm not surprised if the binding code generation can't handle a union with it yet. Note also this in WebIDL: https://webidl.spec.whatwg.org/#limit-bigint-numeric-unions - while WebIDL support for a union of bigint and another numeric type is desired , there is a request to file an issue so that the problem can be discussed. And... from that bug tracker, it doesn't look like anyone has actually done it yet.
fdwr commentedon Feb 17, 2024
https://webidl.spec.whatwg.org/#limit-bigint-numeric-unions
Joshua: I see. Well the point in this case is to preserve values all the way through and avoid precision errors. I see one existing issue here whatwg/webidl#959 (but oddly empty and already closed).
inexorabletash commentedon Feb 17, 2024
Yeah, I think the concern (from the WebIDL editors) is that they want to ensure that it's going to be used correctly (as proposed here) with handling at the C++ (etc) layer that preserves full precision either as a float64 or bigint. The WebIDL editors just don't want to do extra work unless it's really needed, and don't want anyone writing such a union unless the precision is actually needed. It absolutely is here... this may just be the first spec where that's actually the case! 🤯
inexorabletash commentedon Feb 29, 2024
Comparing the blink bindings implementation for unions and the spec for union conversions, it looks like the cases for bigint are simply missing i.e. not implemented yet.
fdwr commentedon Apr 11, 2024
We have some parameter validation discussions happening in the fill-sequence constant overload CR. I'm content to restrict this sequential fill overload to reject infinity as an input (to simplify parameter validation) so long as we have some other means of creating tensors filled with such values; and I propose we repurpose the existing
constant(value, type)overload to insteadconstant(descriptor, MLNumber), which accepts any possible value for that data type from the caller (including infinity and NaN, which are valid representations for floating point numbers). Thoughts?fdwr commentedon Apr 12, 2024
We're deciding between (a) vs (b):
(a) 3 separate functions, one consuming buffers, one for constant fills, one for sequence fills:
➕ more direct
(b) 2 functions, one consuming buffers, and one that takes an options object with optional params:
Credit @a-sully
➕ pretty immediately clear to the reader, without needing to lookup whether parameter 2 or 3 is the step.
wacky6 commentedon Apr 12, 2024
This seems nice from caller's perspective.
But I think we'll need hand-written parsing logic.
I don't think WebIDL binding generator is smart enough to tell different kinds of dictionaries apart.
dictionary FillConstant{ fill: MLNumber // or `start` }; dictionary FillWithSequence { start: MLNumber step: MLNumber }a-sully commentedon Apr 12, 2024
Yup! That recommendation is based on guidance here: https://w3ctag.github.io/design-principles/#prefer-dictionaries
And my suggestion for combining the "fill with a given value" and "fill with this value + a step" methods into one is based on the guidance here: https://w3ctag.github.io/design-principles/#optional-parameters
If the dictionary argument itself is optional, then just this is sufficient:
I'm not sure, though as @fdwr mentioned above I think if we use
valueinstead ofstartthat might be sufficient for both use cases?a-sully commentedon Apr 12, 2024
Taking a step back and looking at the problem statement described in the issue description, I'd like to poke at this claim:
Let's first look at the Problematic Library differences:
PyTorch seems to have resolved this by deprecating
rangein favor ofarange, which behaves the same as TF, Python's builtinrange(), numpy'sarange, and also Core ML's equivalent. Each of these operators takestart,end, andstepargumentsSo there's no problematic library difference, right?...
...What about DirectML?!
DirectML does not require an explicit
endparameter, instead inferring the endpoint from the dimensions (as this issue proposes to do for WebNN). But this has a few implications:Infinite
end@fdwr threw out the following scenario over on the Chromium code review:
This makes sense in DML, which (according to what @fdwr tells me :P ) will gladly can saturate floats to
infonce they exceed the max valueThis does not make sense for the other frameworks, which require a finite
endvalue:This means that even if we decide that an
endvalue does not need to be specified via WebNN - since we can infer it fromstart + step * size- we must be able to compute it to a finite valueBut even if it's finite, can we be sure the values are filled as we expect?
Quirks of floating point math
Say you want to fill a tensor of shape (10,) with evenly-spaced float16 values from 0 to 1. In the original IDL, this might look like:
This maps closely to the (non-DML) APIs described above. For example:
DML, on the other hand, (according to their docs) performs the following pseudocode:
The values are different!
The numpy docs have an explanation:
and also
A quick check of TFLite and PyTorch show the same behavior. Core ML's
rangeis implemented usingnp.arange. And Python's built-inrangefunction sidesteps this problem by only supporting integersAnother thing to consider are the calculations needed by the caller themselves. In the case above, the caller has
start,end, and dimensions. If the WebNN API surface includes astart,step, and dimensions, then the caller will have to computestepmanually. This computation itself has the potential to introduce unwanted imprecisionSo what should we do?
In order to ensure we get the same values across platforms, I propose we specify the behavior of
np.arange. Concretely, this means:start,step, andend, as well as the dimensions (and dtype)dtype(start + step) - dtype(start)ceil((stop - end)/step)Chromium's DML implementation can then use
startand internalStep - rather than thestepvalue passed from JS. I believe that should give us the same behavior across all platforms 🤞Meanwhile, requiring a finite
endvalue sidesteps the whole "infiniteend" problemIf we go down this route, then I think three overloads probably makes sense? :)
a-sully commentedon Apr 16, 2024
Taking an even bigger step back, I was curious what the rationale for adding this operator (which I'll refer to as
fillSequencebelow) was in the first place, since this functionality can be achieved by filling anArrayBuffer(orMLBuffer, soon #614 (comment)) from JavaScript and passing it as aconstant()... From what I can tell based on digging through old issues and PRs, the rationale for adding this operator can be traced back to this comment by @wchao1115#478 (comment) (copied below)
In light of the recent discussions on #614 about achieving minimal buffer copies by using
MLBuffer, I wonder whether the optimization promised byfillSequenceis still worthwhile? Recalling the conclusions from #614 (see #614 (comment)):Passing an
MLBufferas aninput()may achieve the same "single copy of the buffer" behavior thatfillSequenceaims to provide. Additionally, this input buffer would only need to be allocated and have its contents computed once, whereas use of thefillSequenceoperator would require re-allocating the buffer and re-computing the sequence each timecompute()is called on theMLGraph. My understanding of the situation is as follows:fillSequenceinput(MLBuffer)constant(MLBuffer)Questions for the group:
???? Are there examples of frameworks which may internally optimize this operator - e.g. by cleverly avoiding realizing the full output tensor?fillSequence()? If so, what are the expected usage patterns?†Hopefully 🤞 Pending further
MLBufferprototyping @bbernharfdwr commentedon Apr 18, 2024
My biggest concern is deducing tensors shapes from wobbly floating point calculations, especially considering the caller (maybe Javascript, maybe compiled WebAssembly, maybe TF with one rounding behavior, maybe PT with another rounding behavior...) and the browser (with its own FPU details) can differ (it would be bad if the browser computed its range subtraction and delta division via float64 whereas the caller used float32, or vice versa), and a mismatch between the output shape can result in the whole graph execution breaking due to incompatible shapes when combined with other operators.
High-level frameworks like TF Lite and PyTorch can do they want and include such helpful functions based solely on FP parameters, but low-level API's like WebNN should take more explicit tensor shapes.
🤔 Seems not so. I picked nice integer numbers for the example above, but more generically, if you pass the same values into
tf.rangeandtorch.arange, you get different values, and more adversely, different shapes:I'd sooner drop this op altogether (and force the caller to fill in the Float32Array) than include it with FP deduced shape.
(update 20240419T0320) I opened a doc fix for the pseudocode. The actual DML output is
[0. 0.1 0.2 0.2998 0.4 0.5 0.5996 0.6997 0.8 0.9 ]. 📖🐞a-sully commentedon Apr 19, 2024
Thanks again for the deep dive @fdwr :)
Just to clarify a couple points...
If we went down this route we would clearly specify the behavior of the browser - say, to always be float64. So if frameworks are doing their parallel calculations in some other data type, that's a bug in the framework and not something we (as builders of the web platform) should be too worried about.
Of course we should strive to design the API such that callers fall into the pit of success. But there's a difference between an API which is unintuitive to use (say, because the parameters are ordered differently from the analogous function you're used to in Python) and one which cannot reliably be used correctly_ (say, if the browser sometimes computes shapes in float32 and other times in float64, and you have no way to know which will be used).
I think the "FP deduced shape" API we're discussing here is the former. But it sounds like (based on comments like the one below) you're suggesting that that may not be realistic, given the discrepancies in the underlying frameworks?
If that's true, I concur:
Recalling the questions I posed to the group earlier...
Unless there are very compelling answers to 2 and 3, I'm in favor of removing this operator. WDYT?
fdwr commentedon Apr 24, 2024
@a-sully : I had to analyze some models deeper first before I could reply. Looking through ~700 models on my mini-collection with 19 having
Rangein them, all the cases (unless I accidentally missed opening one) turn out to either:If we encounter a more compelling case later where a large fill directly on the GPU is worthwhile, then we can consider re-adding fillSequence (with explicit shape parameter, and only computing once rather than each
computecall). Until then, letting the caller just fill in a little array with numbers (with their framework idiosyncrasies intact) sounds fine, and we can remove this operator. I'll talk with Miao and Ningxin in a few minutes for their take... ⏱️.a-sully commentedon Apr 25, 2024
Thanks again for the investigations @fdwr! I just put up #656 :)
a-sully commentedon Apr 30, 2024
The above PR merged. Let's close this issue?