[ANN] pre128: preallocating wrapper for big.Int

[speter]

I have created a thin wrapper package for math/big (big.Int) that allocates an array together with a big.Int and uses it as the initial slice. With this package, "NewInt(x)" only uses one allocation instead of two, and "z.SetInt64(x)" on an uninitialized Int uses no allocations instead of one.

Programs and packages that use big.Int in a self-contained manner can use it as a drop-in replacement for math/big. In addition, NewIntBig(x), Int.SetBigInt(x), Int.BigInt() are provided for interoperability.

Install: go get speter.net/go/exp/math/big/pre128
Import:  import big "speter.net/go/exp/math/big/pre128"
Docs:    http://speter.net/go/exp/math/big/pre128

As the package name suggests, this version preallocates 128bits, but adjusting it to other sizes is trivial. I have adapted most of the tests for type Int in math/big and those pass but they are disabled for now as the results depend on the Go version (waiting for the build tag for go1.1).

Wrappers for type Rat are not implemented. Wrapping Word in a manner that is API-compatible with math/big requires unsafe; API-incompatible workaround implementations are provided for environments that disallow unsafe.

Whether this brings an overall improvement depends on application access patterns and is yet to be seen. However, use cases which allocate relatively many instances and do relatively few operations on each are more likely to benefit.

Any feedback is welcome.

Peter

[Carlos Castillo]

Is there any reason why your package just can't return the original big.Int after pre-allocating: http://play.golang.org/p/WVYWQdtoV- . It doesn't look like your code has any extra functionality on-top of the pre-allocation, so there shouldn't be any need to create a structure where 99% of the code serves to delegate to the internal big.Int value.

It would be less fragile, as a significant change to math/big can easily break your package (or make it less useful due to missing functions), and since it is returning a *big.Int, there isn't the issue of interoperability with existing code that expects *big.Int (no need to pack/unpack big.Int into/from pre128.Int). Also no need for unsafe, and the lack of delegation means that it won't be potentially slower than big.Int.

As a side note, I'm not sure (one of the runtime devs can correct me if I'm wrong), but putting the big.Int(no pointer), and the array in the same struct, means that for the life-time of the big.Int, both the big.Int and the array must be allocated, even though if you have a big.Int big enough to exceed the space of your pre-allocation it cannot be collected. IE: putting a value larger than 2^128 inside a pre128.Int requires the big.Int code to allocate a new slice with more words than pre128's preallocation, but the preallocation can't be collected because it's part of a struct which is in use for the big.Int field. Therefore your code (and mine as well) will hold on to extra, unusable memory, should the pre-allocation not be large enough.

[speter]

Thanks for the comments. (Sorry I was "off the grid" for a couple of days.)

On Sat, Nov 17, 2012 at 7:40 PM, Carlos Castillo <cook...@gmail.com> wrote:

Is there any reason why your package just can't return the original big.Int after pre-allocating: http://play.golang.org/p/WVYWQdtoV- . It doesn't look like your code has any extra functionality on-top of the pre-allocation, so there shouldn't be any need to create a structure where 99% of the code serves to delegate to the internal big.Int value.

The reason is that NewInt() is only one of the many ways for creating big.Ints. It should be relatively straightforward to modify programs using `new(big.Int)` or `var x big.Int` to use NewInt() instead, but I can't think of an easy way to adapt programs that use big.Ints (not *big.Ints) in slices, arrays, or maps.
 

It would be less fragile, as a significant change to math/big can easily break your package (or make it less useful due to missing functions), and since it is returning a *big.Int, there isn't the issue of interoperability with existing code that expects *big.Int (no need to pack/unpack big.Int into/from pre128.Int). Also no need for unsafe, and the lack of delegation means that it won't be potentially slower than big.Int.

Given the backwards compatibility guarantee for the Go standard library packages, I wouldn't consider it fragile. It is not so often that methods / functions are added to math/big, and when it happens, it should be fairly easy to add wrappers for them, once a convention such as http://code.google.com/p/go/issues/detail?id=4116 is established. There is another "compatibility" issue between tip and release due to a bug for which a fix hasn't been released in go1.0.x, but this should be resolved soon too. (I am also not very happy about the need for using unsafe in this case, and I have been meaning to post a separate question regarding that matter, but I was holding off because I wouldn't have been able check the answers.)

Although there may be some overhead due to delegation, I am thinking that in the cases where preallocation can avoid additional allocation, the overhead for delegation could often be less than that for the extra allocation and related garbage collection. (I hope to do more evaluation on this when I have more free time.) In addition, I am not sure how much of it is currently being done by the compilers (and linkers), but ideally optimizations could eliminate much of the delegation overhead.

Ultimately if someone finds preallocation beneficial for their programs but want to avoid any delegation overhead, they may want to use math/big directly and preallocate "manually". Even for such cases, I am hoping that the drop-in-replacement nature of the package could make it useful in initially assessing the potential benefits of preallocation.

 

As a side note, I'm not sure (one of the runtime devs can correct me if I'm wrong), but putting the big.Int(no pointer), and the array in the same struct, means that for the life-time of the big.Int, both the big.Int and the array must be allocated, even though if you have a big.Int big enough to exceed the space of your pre-allocation it cannot be collected. IE: putting a value larger than 2^128 inside a pre128.Int requires the big.Int code to allocate a new slice with more words than pre128's preallocation, but the preallocation can't be collected because it's part of a struct which is in use for the big.Int field. Therefore your code (and mine as well) will hold on to extra, unusable memory, should the pre-allocation not be large enough.

You are right about the preallocated array not being freed when the slice is reallocated, but I think that cases where such excess memory usage would become an issue (cases where a large portion of the values handled do not fit into the preallocated array) are cases to which preallocation is not very well suited anyway.

Peter

 

 

On Saturday, November 10, 2012 6:19:31 PM UTC-8, speter wrote:

I have created a thin wrapper package for math/big (big.Int) that allocates an array together with a big.Int and uses it as the initial slice. With this package, "NewInt(x)" only uses one allocation instead of two, and "z.SetInt64(x)" on an uninitialized Int uses no allocations instead of one.

Programs and packages that use big.Int in a self-contained manner can use it as a drop-in replacement for math/big. In addition, NewIntBig(x), Int.SetBigInt(x), Int.BigInt() are provided for interoperability.

Install: go get speter.net/go/exp/math/big/pre128
Import:  import big "speter.net/go/exp/math/big/pre128"
Docs:    http://speter.net/go/exp/math/big/pre128

As the package name suggests, this version preallocates 128bits, but adjusting it to other sizes is trivial. I have adapted most of the tests for type Int in math/big and those pass but they are disabled for now as the results depend on the Go version (waiting for the build tag for go1.1).

Wrappers for type Rat are not implemented. Wrapping Word in a manner that is API-compatible with math/big requires unsafe; API-incompatible workaround implementations are provided for environments that disallow unsafe.

Whether this brings an overall improvement depends on application access patterns and is yet to be seen. However, use cases which allocate relatively many instances and do relatively few operations on each are more likely to benefit.

Any feedback is welcome.

Peter

--
 
 

[Carlos Castillo]

You didn't really answer the question: Does your code actually need new types? As far as I can tell, the answer is no, since I can create a NewInt() function which pre-allocates space inside a math/big.Int and returns the big.Int. For the reasons I mentioned earlier, a math/big.Int is preferable to a pre128.Int since it is guaranteed to be more compatible with existing code, and is future-proof with little to no effort, and there is no need for "unsafe" which is unusable for some users. Sure you could write a better wrapper, and keep it up to date, but it would still require a far greater amount of effort to maintain/update than my suggestion, which in most cases would require no effort.

An additional drawback to your method is that it is currently not possible to create an array/slice/map of pre128.Ints the same way you create an array of math/big.Ints. If you write "x := make([]pre128.Int,128)", the pre.NewInt code which does the preallocation isn't called, so the extra memory for the preallocation in the pre128.Int is not used, and nothing is pre allocated. You can do the following to call pre128.NewInt:

x := make([]*pre128.Int,42)

for i := range x {

x[i] = pre128.NewInt(0)

}

But this is nowhere near as good as it can get. I've written a "NewInts(n int) []big.Int" function that has only 2 *total* allocations, as opposed to the above n+1 allocations.

My suggestion is to remove your type as it currently adds no functionality (the pre-allocation is performed by the NewInt() function, not the type), and you will have a package that is far more compatible and lightweight (only one or two functions). You could also add functions to pre-allocate a large number of big.Ints since that will off far greater runtime savings.

I'm also not sure on your assertion that the pre128.Int will be faster in most situations since I see 3 common situations:

1. A small number of big.Ints() used sparingly, where using pre128.Int is essentially a premature and unnecessary optimization.
2. A small number of big.Ints() used repeatedly, where the time saved by the single allocation using pre128.Int will eventually be overshadowed by all the other computations, more so if delegation has any cost.
3. A large number of big.Ints() where there are better ways to pre-allocate them then calling pre128.NewInt() in a loop.

Now to avoid being entirely negative, I did like your constant arithmetic to portably compute the number of big.Words needed to store 128 bits, since it avoids making multiple files guarded by build flags for each architecture where the size of uintptr could be different.  

[Michael Jones]

If this makes sense then lets just change nat.

> --
>
>



--
Michael T. Jones | Chief Technology Advocate | m...@google.com | +1
650-335-5765

[Carlos Castillo]

speter,

After looking at your code again, I saw where you were catching the case of someone creating a "raw" pre128.Int variable, array, slice, or map. I'm not sure how I missed it before. So to revise my previous statement, yes your code does do something useful with the new type. I did leap to some conclusions about the operation of your code which were false, and I even did read it once... sorry.

However, I think it's still possible to make a package that either creates new pre-allocated *big.Ints, or could pre-allocate an array/slice of "raw" big.Int values. Obviously this would not be automatic, like your code, but it would be more interoperable with existing code (not that interoperability was your priority).

Of course, if the go-devs go for modifying big.nat to have the initial storage preallocated (as Michael is suggesting), that would be the best solution, provided the potentially wasted memory & code change produce acceptable gains.

I think I'll post how I think preallocation could work to github so you or others can see where I'm coming from.

[Carlos Castillo]

As promised I have posted my package. It is very raw, but has documentation and examples for each utility function.

documentation: http://go.pkgdoc.org/github.com/cookieo9/go-misc/big128

source: https://github.com/cookieo9/go-misc/tree/master/big128

import "github.com/cookieo9/go-misc/big128"

[speter]

I have updated the documentation to clarify that the semantics for assignment of Int values is different from that in math/big. (Although it could be argued that programs shouldn't rely on the internal structure of Int that is unexported and could change anyway.) Assignment of *Int values, which should be much more common, is not affected.

Peter

[speter]

> I'm also not sure on your assertion that the pre128.Int will be faster in most situations

I probably should have been more explicit about this from the beginning, but let me clarify this to prevent further misunderstanding: I did not mean to assert that preallocation is "faster in most situations".

First, there is only overhead when handling values that don't fit in the preallocated array. Second, I'd like to reiterate my prior statement: "use cases which allocate relatively many instances and do relatively few operations on each are more likely to benefit."

It is also possible that due to the allocation overhead, big.Int has previously been avoided in the situations when preallocation would be beneficial. So I think there is a chance for preallocation to be useful is some situations even if it turns out that it only brings overhead to some or most existing use cases of Int. (Unfortunately I haven't had time to do thorough evaluation for different use cases but I hope to do so.)

To be more specific, the use case I had in mind was decimal calculations where the significand (aka coefficient / mantissa) can exceed 64 bits but often doesn't. If someone has other use cases which uses integers that are potentially bigger than 64 bits but usually not "very" big, please share them.

Peter

--
 
 

[speter]

Carlos,

Thanks for the comments, and sorry again for the long delay (hopefully I can be more responsive from now on).

I think both approaches have their pros and cons. Compared to the approach of your package, these are what I consider to be the pros of the approach in my package (these assume that the caller packages don't directly assign Int values):

1. IIUC, the helper functions in your approach (and mine and the ones in math/big as well) will always allocate on the heap, but with my approach it is also possible to avoid heap allocations using `z := new(pre128.Int).SetInt64(x)` or `var z pre128.Int; z.SetInt64(x)` (when the address doesn't escape).

2. It supports all types involving Int, including arrays of any size, or slices of a struct containing Int's. (This may not be very common but happens to be used in the case I originally had in mind for decimals.)

3. When applying it to an existing package (or group of packages) that uses big.Int in a self-contained manner (not exchanging *Ints with other packages), only import statements need to be changed. That is, there is no need to look through the code to find and change all allocations, or to learn new APIs.

4. Even when there is a need to exchange *Ints, only the places that interact with external packages need to be changed. This means that ideally the "main business logic" parts can remain intact. I also believe that it is usually easier to find and change all places where data is exchanged with external packages than to find and change all allocations.

Peter

--
 
 

[speter]

Michael,

Thanks for looking at this. I'd be glad if preallocation made it into math/big, and I would have suggested including it, but I myself have a couple of concerns.

The first one is evaluation (which I assume is what you meant by "if this makes sense") which in itself is not entirely straightforward, but I plan to keep working on it. (I will probably need to ask for help later on on how to properly evaluate the effects of allocations and GC.)

The second one is compatibility. As I have mentioned in a previous message, preallocation (with the approach implemented in my package) changes the semantics of the assignment operation for Int (and Rat as well if implemented in big.nat). I have read through the Go1 guarantee again and I tend to think that this change could be acceptable under the "unspecified behavior" clause, as neither the internal data structure nor the assignment semantics is explicitly specified in the docs for math/big, but I'd like to make sure that the Go devs agree. Could I ask for your opinion on this?

A specific example of code for which the behavior changes (also at http://play.golang.org/p/Rr4_KC_3Wc ):

var a, b, c big.Int
a.SetInt64(1)
b.SetInt64(2)
c = b
b = a
fmt.Println(&a, &b, &c)
// go1.0.3: 1 1 2
// with preallocation: 1 1 1

If this change is not considered to be an issue, I'll prepare a CL with preallocation implemented in big.nat that makes experimenting with and evaluating preallocation easier.

Peter

--

[Jan Mercl]

On Wed, Dec 12, 2012 at 12:54 AM, speter <spete...@gmail.com> wrote:
> A specific example of code for which the behavior changes (also at
> http://play.golang.org/p/Rr4_KC_3Wc ):
>
> var a, b, c big.Int
> a.SetInt64(1)
> b.SetInt64(2)
> c = b
> b = a
> fmt.Println(&a, &b, &c)
> // go1.0.3: 1 1 2
> // with preallocation: 1 1 1
>
> If this change is not considered to be an issue, I'll prepare a CL with
> preallocation implemented in big.nat that makes experimenting with and
> evaluating preallocation easier.

This would be a (Go 1 promise) breaking change. Even worse is that old
code continues to compile while silently failing to do what it was
doing before. IOW, please don't do that.

-j

[Carlos Castillo]

People using big.Int that way are already doing something wrong because copying big.Int values only does a shallow copy of a deep type.

eg: http://play.golang.org/p/0IbT0fnfUr

Note that a single Set() operation affects two "Values". I doubt people wanted this behaviour when they set b = a. Any code that copies big.Int values using go's = operator is going to be a minefield down the road even if big.Int is never changed. This mistake is very similar to (and is in fact related to) copying one of go's reference types (slice, map, chan) where the user believes they are getting a completely new copy of something when it is still attached to the old version.

Should I file a bug about this? Right now it seems as though the best option is to update the big.Int documentation warning people against writing code like the example. Anything done to fix it (if possible) could change the behaviour of established code.

[Jan Mercl]

On Wed, Dec 12, 2012 at 12:54 PM, Carlos Castillo <cook...@gmail.com> wrote:
> People using big.Int that way are already doing something wrong because
> copying big.Int values only does a shallow copy of a deep type.

Not really relevant. The problem is not in this. The (introduced)
problem is that `b = a` would now change value of `c`. That's quite
surprising IMO.

> eg: http://play.golang.org/p/0IbT0fnfUr
>
> Note that a single Set() operation affects two "Values". I doubt people
> wanted this behaviour when they set b = a. Any code that copies big.Int
> values using go's = operator is going to be a minefield down the road even
> if big.Int is never changed. This mistake is very similar to (and is in fact
> related to) copying one of go's reference types (slice, map, chan) where the
> user believes they are getting a completely new copy of something when it is
> still attached to the old version.

Slices are value types, their instances (internally) reference a
backing array. They are passed by copy commonly. Moreover, the
behavior is (now) consistent with (current) big.Int:

http://play.golang.org/p/HHM4Pp-F_m

There are legitimate uses for slice (values) sharing the backing
array. Actually that's the way they're usually used. It's not
surprising when mutating the backing array the change may be observed
via all of the slice _copies_. All of this holds for big.Int in the
very same way. It is surprising when mere copying a value (slice or
big.Int) changes another, not involved value. By value I mean the
big.Int, not it's backing []Word - consistently with how slices work.

-j

[Carlos Castillo]

The value of c changing is no more or less surprising than the current behaviour where changing a modifies b. At some point it was assigned the value of b, so some if its pointers are pointing at shared data. 

Slices can operate the way they do because they are transparent in their operation. In the language specification it states how slices operate, and some of the pitfalls to avoid. A programmer who fails to read the documentation on how slices work will write buggy code if their expectations don't match the openly documented behaviour.

A big.Int value, is not documented the same way. As it is written it is fully possible to create a big.Int value, copy it into another variable, and the documentation doesn't seem to specify what's supposed to happen. If people are expecting it to behave like a regular int value, they will be surprised by my example, and it will be very hard to debug. The current behaviour is in fact not entirely consistent with a reference type (like a slice) as some state (the magnitude) is shared, while other state (sign) is not: http://play.golang.org/p/xH9jDSTKNK

From where I stand, there is currently surprising and undocumented behaviour at play when big.Int values are copied. One way to deal with it would be to add documentation that tells users that they should not copy values of these types, leaving behaviour of such as undefined. If this were the case, Peter's patch would seem to only change undefined behaviour and thus not violate the Go 1 promise. If this is behaving as expected/intended, then I suggest that documentation is added to reflect this, and Peter's proposal be considered for Go 2, or for whenever the Go 1 promise no longer applies.

Also, the preallocation semantic change is consistent with the current behaviour of bytes.Buffer (which itself uses preallocation) http://play.golang.org/p/TrFcsUcw5i

[Jan Mercl]

On Wed, Dec 12, 2012 at 3:25 PM, Carlos Castillo <cook...@gmail.com> wrote:

> http://play.golang.org/p/xH9jDSTKNK

You now seem to agree, that the not involved `c` is (consistently) not
affected (now). But (inconsistently) it will be (only big.Int `c`,
after the change).

> http://play.golang.org/p/TrFcsUcw5i

I disagree that this is related to the problem being discussed.

Sum of my POV: Both a slice and big.Int are value types containing
some unexported bookkeeping data with a (possibly shared) backing
array. They behave consistently in the same way, where 'a = b` cannot
change 'c' in Peter's original code
http://play.golang.org/p/Rr4_KC_3Wc. The discussed change would
surprisingly allow the 'colateral damage' made to `c` and is also
backward uncompatible, breaking the Go 1 promise. It doesn't matter,
how silly or clever any code using this may be. It is not a bug to
rely on such behavior based on the aforementioned promise as long as
the original behavior covered by the promise is not a bug per se.
Additionally that behavior is consistent with how an analogous thing
(slices) behave, so it's not even special.

-j

[speter]

I think my question is better split into two questions:

1. Is my interpretation correct that the semantics of assignment operation for big.Int values is not specified for Go1?

2. If so, is this an omission (and the behavior should be explicitly specified in the docs) or is it really OK to allow changes to the behavior of assignment for big.Ints?

I agree that it may be considered "surprising behavior", and maybe just because of this, I also thought at first that it would probably be against the Go 1 promise. But going through it again I tend to think that it doesn't. More specifically, I think the semantics of the assignment operation for big.Ints is not part of the Go specifications: although the assignment operation for structs is specified, what data actually gets assigned as part of big.Int and how that data is used / interpreted is not part of the specification, and so is not covered by the guarantee. Thus I think that programs relying on any specific behavior after assignment are not legal (yes, that likely includes some code written by myself as well). Note that in contrast, assignment of *big.Int values and use of the Set*() methods is well specified.

But of course it is possible that my interpretation is mistaken. I'd be glad if you could tell me which specific part(s) of the Go 1 promise you think it breaks.

Peter

[Jan Mercl]

On Wed, Dec 12, 2012 at 4:13 PM, speter <spete...@gmail.com> wrote:
> But of course it is possible that my interpretation is mistaken. I'd be glad
> if you could tell me which specific part(s) of the Go 1 promise you think it
> breaks.

[Q]
Go 1 defines two things: first, the specification of the language; and
second, the specification of a set of core APIs, the "standard
packages" of the Go library. The Go 1 release includes their
implementation in the form of two compiler suites (gc and gccgo), and
the core libraries themselves.

It is intended that programs written to the Go 1 specification will
continue to compile and run correctly, unchanged, over the lifetime of
that specification. At some indefinite point, a Go 2 specification may
arise, but until that time, Go programs that work today should
continue to work even as future "point" releases of Go 1 arise (Go
1.1, Go 1.2, etc.).
[/Q]

src: http://golang.org/doc/go1compat.html#introduction

-j

[speter]

Thank you, I've read that, and based on that (as I've explained in more detail above) my interpretation is that the semantics of the assignment operation for big.Int values is not covered by the "Go 1 specification" that the above text refers to, so it does not break this part.

Peter

[Jan Mercl]

On Wed, Dec 12, 2012 at 4:58 PM, speter <spete...@gmail.com> wrote:
> Thank you, I've read that, and based on that (as I've explained in more
> detail above) my interpretation is that the semantics of the assignment
> operation for big.Int values is not covered by the "Go 1 specification" that
> the above text refers to, so it does not break this part.

How do you interpret the second paragraph?

----

It is intended that programs written to the Go 1 specification will
continue to compile and run correctly, unchanged, over the lifetime of
that specification. At some indefinite point, a Go 2 specification may
arise, but until that time, Go programs that work today should
continue to work even as future "point" releases of Go 1 arise (Go
1.1, Go 1.2, etc.).

----

Specifically

"will continue to compile and run correctly, **unchanged**,"

and most importantly

"**programs that work today should continue to work even as
future "point" releases of Go 1 arise**".

(Emphasizes mine)

My interpretation is that what's shown in
http://play.golang.org/p/Rr4_KC_3Wc doesn't make the cut.

-j

[Carlos Castillo]

Also from the same document:

Unspecified behavior. The Go specification tries to be explicit about most properties of the language, but there are some aspects that are undefined. Programs that depend on such unspecified behavior may break in future releases.

Both Peter and I seem to agree that what is happening in http://play.golang.org/p/Rr4_KC_3Wc, is a case of unspecified behaviour changing. It is unspecified because nowhere in the public API is the semantic result of copying big.Int values ever mentioned. In fact it is easily possible to create three different implementations of the same interface that each behave differently when copied: http://play.golang.org/p/zc11r7oUOD

Neither current big.Int (which acts like B), nor bytes.Buffer (which acts like C), specify that a non-pointer value acts any differently than an integer (type A) when copied with =, but as I have shown, they do, and there is no way to tell from the go 1 specification alone. The proposed change would have the side-effect of turning big.Int from acting like B, to acting like C, which the "unspecified behaviour" clause would seem to allow.

[speter]

I'd emphasize "**programs written to the Go 1 specification** will continue to compile and run correctly, unchanged". That is, I think the question is whether the specification mandates that the example program outputs "1 1 2" (which I think it doesn't), or it is an artifact of the current implementation.

For the second quote, this sentence by itself doesn't make it explicit, but I think in the context after the previous sentence, and considering the specific clause later about "unspecified behavior", it seems clear to me that promise is intended to apply to matters described in the specification.

Peter