Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[RFC] Promotion rules for overflow reduction #167

Closed
kimikage opened this issue Jan 15, 2020 · 13 comments
Closed

[RFC] Promotion rules for overflow reduction #167

kimikage opened this issue Jan 15, 2020 · 13 comments

Comments

@kimikage
Copy link
Collaborator

kimikage commented Jan 15, 2020

We plan to implement the overflow-checked arithmetic to mitigate the overflow problem (cf. #41, #152).

The checked arithmetic prevents numerical errors which the users do not intend, but it is up to the users to correct them. There are two major issues.

  1. The current Normed cannot represent negative numbers, so we will easily encounter OverflowError in subtraction.
  2. The return type of addition/subtraction is the same as the input type, so it needs to convert values into wider type (e.g. Float32) to avoid overflow.

To solve the former, signed Normed is proposed in PR #143.
I don't agree with the introducing Normed{<:Signed} because of the huge impact on compatibility. However, I think signed Normed is not so bad unless it breaks the existing Normed.

For the latter, PR #143 also proposes type promotions.
I don't consider the latter a fatal problem, as it's up to the users what operations and types they want. On the other hand, the type promotion has some problems.

Perhaps you might think that the type promotion frees you from the overflow problems.
But I think it is an illusion. To turn and face reality, let's decide the promotion rules.

Of course, the preferred promotion rule for me is "not to promote".

@kimikage
Copy link
Collaborator Author

Some suggestions are shown schematically for reference. All have drawbacks.

"Always" rule

always


"Half" rule

half


"Last-One" rule

lastone


"N0f8/N0f16" rule

n0f8


"Floating-Point" rule

float

@timholy
Copy link
Member

timholy commented Jan 15, 2020

Let's break my proposal into two steps:

  1. broadening Normed{T<:Unsigned, f} to Normed{T<:Integer, f}
  2. modifying the arithmetic rules to return different types than the input arguments

I don't think 1. needs to break the existing Normed code. Mistakes in implementation might do that, and of course handling a wider array of types could theoretically increase complexity and/or introduce performance problems, but my crystal ball predicts that we can handle this.

Item 2. is the more controversial issue, and I'm not interested in working on 1. unless we can come to some kind of consensus. I have thought most about 3 options:

  • keep the current system: output types are the same as the input types (this leaves overflow common)
  • N0f8(0.2) - N0f8(0.4) returns S7f8(-0.2), where const S7f8 = Normed{Int16,8}
  • N0f8(0.2) - N0f8(0.4) returns S6f8(-0.2), where const S6f8 = Normed{NInt16,8}, where NInt16 is defined as a new integer type (from a NaNIntegers package, here's a start) that uses the next-to-top bit as a NaN flag.
  • EDIT: N0f8(0.2) - N0f8(0.4) returns -0.2f0

For the last two options, once you get to an Skfn type there is no more type-changing in arithmetic operations (i.e., "promote N->S but then no more promotion").

The last two differ on what you want out of the system: Normed{Int16,8} makes "easy things easy" (e.g., img1 .- img2) but introduces traps for the unwary, e.g., for i = 1:n; imgaccum .+= img[i]; end. We have the same problem now, but one could argue that by making it less common it's potentially more dangerous. The more positive viewpoint is that it's really annoying that currently one can't write img1 .- img2 and inspect the result; when I'm writing "real code" I'll be more careful, but I do want exploratory stuff to be dirt-simple.

Conversely, Normed{NaNInt16, 8} would let you detect overflow robustly. However, it is likely to reduce performance. If the hit is big it will not be sustainable as a foundation for image processing, and since that's the whole purpose I created the Normed types in the first place then I wouldn't regard that as acceptable.

Of course we can write NaNIntegers and see what happens; moreover, if we take step 1. then it becomes possible to support them with this package. But we do have to decide the arithmetic rules, and there a choice is necessary.

@timholy
Copy link
Member

timholy commented Jan 15, 2020

That's a beautiful diagram. Can you explain it a bit?

@kimikage
Copy link
Collaborator Author

For the last two options, once you get to an Skfn type there is no more type-changing in arithmetic operations (i.e., "promote N->S but then no more promotion").

I think the rules are really practical, but too ad-hoc. FixedPointNumbers is in JuliaMath, not in JuliaGraphics or JuliaImages, so the behavior is somewhat strange from a neutral point of view.

@timholy
Copy link
Member

timholy commented Jan 15, 2020

If you're going to promote, you have to get to a fixed point wrt the type system very quickly. If your diagram proposes a scheme whereby N0f8s could become N8f8s which could become N24f8s, I don't think that's viable. Inference will hate us.

In my mind, there are basically two sensible options: "don't widen" and "widen all the way immediately." My proposal falls in the latter camp, where "all the way" is defined as something with twice the number of bits. (We could go to machine precision, e.g., UInt, but for image processing that's too big.)

@kimikage
Copy link
Collaborator Author

kimikage commented Jan 15, 2020

I don't think that's viable.

I agree with you. I showed "bad" examples to clarify the negative aspects of the promotion.

That's a beautiful diagram. Can you explain it a bit?

The above diagram does not clearly distinguish signed Normed from unsigned Normed because I don't like the fact that promotion rules differ with or without sign.
Each box represents a type. For example, the box in the upper right corner means N7f1 or S6f1.
The arrows represent promotion rules. For example, in the "Always" rule,

  • ::N0f8 + ::N0f8 -> ::N8f8
    • ::N8f8 + ::N8f8 -> ::N24f8
      • ::N24f8 + ::N24f8 -> ::N56f8
        • ::N56f8 + ::N56f8 -> 💥
  • ::N0f8 - ::N0f8 -> ::S7f8
    • ::S7f8 - ::S7f8 -> ::S23f8
      • ::S23f8 - ::S23f8 -> ::S55f8
        • ::S55f8 - ::S55f8 -> 💥

Thus, the "Always" rule is a nightmare.

I think at least the promotion chain should be broken somewhere. My hope is that it will take place on the 0-th stage, not the first stage. 😄

@timholy
Copy link
Member

timholy commented Jan 15, 2020

Yeah, the "Always" rule is definitely not viable, and we can discard it now. (Consider a container a and the following operation:

s = first(a)
for x in Iterators.drop(a, 1)
    s += x
end

Quiz question: what type is s? That's the question inference will ask.) I'd guess the "Floating-Point" rule would be in the same category, right?

Of the remainder, IIUC they don't promote at all for most types, right?

@kimikage
Copy link
Collaborator Author

For loops, the rules of promoting only once are also problematic. What is the intent of taking a loop quiz here? If you allow the promotion one time, that is just "ad-hoc".
If users have to pay attention to where their data are promoted, why not pay attention to overflow? 😝

I'd guess the "Floating-Point" rule would be in the same category, right?

That's right. The chained promotions are never good. Non-cascading "Floating-Point" variants are logically possible options, but
as you know, there are problems with accuracy.

Anyway, the important thing is not to convince me, but to make FixedPointNumbers better.

@timholy
Copy link
Member

timholy commented Jan 15, 2020

We do have union-splitting, so when there are only 2 choices it wouldn't be a disaster, but the better way to write that loop would be

s = plustype(first(a))            # `plustype(x)` equivalent result to `x + zero(x)`
for x in Iterators.drop(a, 1)
    s += x
end

You can't even implement a useful form of plustype for the "Always" strategy, whereas you can for the "widen immediately" strategy. Nevertheless, the likelihood that some coders will forget plustype and thus trigger union-splitting in callers is one of the better arguments against any form of widening.

If users have to pay attention to where their data are promoted, why not pay attention to overflow? 😝

Agreed that one has to pay attention somewhere. The issue is that when you're doing interactive data analysis img1 - img2 is really attractive and a shame to make much more complicated. Right now the best alternative is float.(img1) - img2. That's not terrible, but neither is plustype(x). Forgetting plustype is arguably less of a mistake than forgetting float, since the former gives slow answers whereas the latter gives wrong answers by colloquial/mathematical (as opposed to computational) definitions of "wrong".

Anyway, the important thing is not to convince me, but to make FixedPointNumbers better.

Agreed & reciprocated. I'm not trying to pretend this is a clear-cut decision even to me. Of the options I listed in #167 (comment) (updated), I think the first, second, and fourth are relatively viable. The NaNIntegers route scares me from a performance standpoint and I'd rather we didn't have to do that. I can live with the status quo (the first option), I just wonder if it's a missed opportunity to make the whole ecosystem better.

@kimikage
Copy link
Collaborator Author

kimikage commented Jan 15, 2020

Another reason the second option is "ad-hoc", is that it is only reasonable with addition/subtraction. For image processing, it may not be a problem. However, if we take up image processing, I think that higher-level packages (e.g. ColorVectorSpace) should handle it. FixedPointNumbers is only part of the ecosystem. It's never bad that low-level packages have low functionality.

@timholy
Copy link
Member

timholy commented Jan 15, 2020

Another reason the second option is "ad-hoc", is that it is only reasonable with addition/subtraction.

That bothers me too. I recently added the fourth option, promote to float, in part for that reason. You've put a lot of effort into accurate and efficient conversions, it might make sense to leverage that more.

I think that higher-level packages (e.g. ColorVectorSpace) should handle it. FixedPointNumbers is only part of the ecosystem. It's never bad that low-level packages have low functionality.

I hadn't considered the idea of having different promotion rules for arithmetic on Color{<:Normed}. That's worth chewing on for a bit.

@kimikage
Copy link
Collaborator Author

As mentioned in #166 (comment), I will change the arithmetic functions in v0.9.0. The changes will include checked_add/checked_sub. The implementation of checked_mul, following checked_add/checked_sub, strongly depends on the promotion rules.
Should I introduce an optimization like #125 (comment)? Or will it become garbage (in the near future)?

@kimikage
Copy link
Collaborator Author

kimikage commented Jul 8, 2020

This discussion seems to be stale. I will start improving the arithmetic functions (cf. PR #190). They may move to another package (something like FixedPointArithmetic) in the future.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants