On Mon, Jun 22, 2020 at 9:45 AM roger peppe <rogpe...@gmail.com> wrote:
>
>
> On Mon, 22 Jun 2020 at 14:26, Andrew Werner <awerne...@gmail.com> wrote:
>
>> Hey Rog,
>>
>> I think I sent you a private reply earlier. My bad. I now see what you're
>> proposing in the first proposal think it makes a lot of sense.
>>
>> The thing that I think I had missed was this piece of magic:
>> // New returns a new Dequeue instance using B as the block storage
>> backing.
>> func New(type T interface{}, *B Block(T))() *Dequeue(T) {
>>
>> One concern I have here is that the `Slice` method is on the array itself
>> so it's possible that invoking it will copy the entire array to the stack.
>> Does that concern you?
>>
>
> It won't copy the array because it's a pointer method (that's what the
> "*B" means).
> In fact it *must not* copy the array because then it couldn't return a
> reference to it.
>
Oh! It’s saying that *B implements the constraint, nifty. Is this idea in
the current proposal? I agree that it’ll do the trick in the same way as
your second proposal and my proposal and is even a bit cleaner. That being
said, it still seems worse than having a mechanism to indicate that a type
really is an array and can be syntactically used as such, no?
I suppose if the Slice method gets reasonably inclined the compiler could
do good things.
I think I’m in favor of this proposal in addition to my proposal that
allows a type to be declared as an array and to thus be used syntactically
as an array.
> The second proposal feels almost identical to what I proposed. Can you
>> help me understand how it differs?
>>
>
> It is indeed a similar approach. The main difference (beyond the somewhat
> simpler dequeue implementation itself) is that my New method returns a
> concrete type, not an interface. This means that it's easier to jump to the
> definition of its method implementations, potentially more performant
> because it can use direct rather than indirect calls (*), and arguably more
> idiomatic Go. It also means it's possible to add more methods without
> breaking backward compatibility, which is a significant benefit in my view.
>
> cheers,
> rog.
>
> (*) you'll still get *some* indirect calls, amortised over the buffer
> size.
>
Ack, sure, thanks for clarifying. No quibbles from me on this front.
FWIW the Alloc* methods came from some experience with these data
structures where I want to decode a stream of structs off the network or
something so I want pointers to zero values to then pass to Decode or
Unmarshal. I’ll admit it feels weird without the context.
>
>>
>> On Monday, June 22, 2020 at 7:58:43 AM UTC-4, rog wrote:
>>>
>>> Thanks for the interesting use case, Andrew!
>>>
>>> I've experimented with a slightly different approach:
>>>
>>> https://go2goplay.golang.org/p/AkqzbWmpj6t
>>>
>>> It expects the caller to implement a method on the array to get a
>>> reference to the
>>> underlying storage, but that's fairly trivial to implement.
>>>
>>> I've built it on top of the "list" package from the stdlib (available in
>>> the dev.go2go branch under src/cmd/go2go/testdata/go2path).
>>>
>>> I think it has the potential to be a bit more performant as the
>>> type-hiding abstraction (Block in my example) is inside the static type, so
>>> most calls can be direct rather than indirect.
>>>
>>> It's *almost* possible to make this implementation use a slice-based
>>> implementation of Block too (thus allowing dynamically specified block
>>> sizes at the cost of an extra indirection through the linked list node).
>>> That's not possible because the pointer method is invoked on the zero-value
>>> of the type, so without using a global variable, there's no way for the
>>> method to find out the required block size. A way to work around that is to
>>> use another level of indirection instead of using pointer methods directly:
>>>
>>> https://go2goplay.golang.org/p/nMreEMpqXd1
>>>
>>> This makes me wonder whether the pointer methods restriction in the
>>> generics draft proposal might not be unnecessary and perhaps not
>>> necessarily a good idea. ISTM that the only reason for restricting methods
>>> to pointer-only is so that they can be called on zero values, and that
>>> necessarily restricts the available parameterisation to static-only (or
>>> using global variables). I suspect that might turn out to be an
>>> anti-pattern. Instead, using function or interface value that operates on
>>> the pointer is strictly more general, I think, and doesn't suffer from that
>>> problem.
>>>
>>> cheers,
>>> rog.
>>>
>>>
>>> On Sun, 21 Jun 2020 at 17:43, Andrew Werner <awer...@gmail.com> wrote:
>>>
>>>> Thanks for the reply! If I read it correctly, it is already possible to
>>>> specify a type constraint as an Array of a given size and so the first part
>>>> of the "What I might have expected" actually does work. I noticed that it
>>>> works in that it works as a type constraint but I found that types
>>>> constrained that way do not support indexing or slicing. Perhaps that's
>>>> just a limitation of the prototype and not the proposal.
>>>>
>>>> The other thing that I think I'm proposing (thanks for the correction)
>>>> is a way to represent all arrays of a given type:
>>>>
>>>> type Array(type T) interface {
>>>> type [...]T
>>>> }
>>>>
>>>> Thanks for dealing with my very long-winded way of saying that.
>>>>
>>>> On Sunday, June 21, 2020 at 12:35:53 PM UTC-4, David Finkel wrote:
>>>>>
>>>>>
>>>>>
>>>>> On Sat, Jun 20, 2020 at 1:22 AM Andrew Werner <awer...@gmail.com>
>>>>> wrote:
>>>>>
>>>>>> [The body of this email is a duplication of the README in
>>>>>> https://github.com/ajwerner/go2dequeue/
>>>>>> which also contains the sample implementation]
>>>>>>
>>>>>> Exercise building a dequeue with the go2 Type Parameter Draft
>>>>>>
>>>>>> This project is an exploration with the go2go / Type Parameters -
>>>>>> Design Draft
>>>>>> <https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md>
>>>>>> with an eye towards block-based data structures which promote access
>>>>>> locality.
>>>>>>
>>>>>> Such data structures traditionally utilize blocks of objects laid out
>>>>>> contiguously in memory. In go, today, one generally specializes such data
>>>>>> structures which are performance critical. This is especially important
>>>>>> in
>>>>>> the case of reducing allocations which occur on critical paths. Using a
>>>>>> sync.Pool can help with allocations in some cases but can be clunky to
>>>>>> use
>>>>>> and, well, do create more pointers for GC to worry about and don't have
>>>>>> the
>>>>>> access locality.
>>>>>>
>>>>>> Whether it's really important to have data structures which include
>>>>>> arrays of other data structures laid out contiguously in RAM is really
>>>>>> important is sort of orthogonal. Let's just assume that it is for now and
>>>>>> look at how we'd do it. We only need to consider rejecting the importance
>>>>>> of this case if we can't find a good solution or idiom to support it. The
>>>>>> google/btree <https://github.com/google/btree> library README links
>>>>>> this Google Open Source Blog Post on block-based container
>>>>>> <https://opensource.googleblog.com/2013/01/c-containers-that-save-memory-and-time.html>
>>>>>> performance indicating it does matter. The interesting thing about that
>>>>>> library is it hardly gets the access locality of the C++ library in the
>>>>>> blog post it references.
>>>>>>
>>>>>> The challenge this library explores is to layout blocks in structures
>>>>>> contiguously in RAM while allowing the user to have some control over
>>>>>> that
>>>>>> block size.
>>>>>> This example
>>>>>>
>>>>>> The approach this experiment takes is to allow the users to specify
>>>>>> the block size by providing a function to map an array type to a slice.
>>>>>> The
>>>>>> allows the blocks to contain a slice which references the array. The
>>>>>> overhead to maintain the slice header is 3 words but the cost is probably
>>>>>> less in memory and more in the optimizations the compiler will be less
>>>>>> able
>>>>>> to perform. In particular, it probably will need to do bounds checking on
>>>>>> that slice and there are probably some opportunities to avoid the pointer
>>>>>> interactions. The interface ends up being pretty reasonable though a
>>>>>> little
>>>>>> bit ... opaque?
>>>>>>
>>>>>> What this looked like in this demo is*
>>>>>>
>>>>>> // Say we want to create a dequeue of things.type Thing struct { Foo
>>>>>> int64, Bar int64, ID [16]byte }// The below incantation will create one
>>>>>> with blocks of 37 elements.d := NewWithArray(func(a *[37]Thing) []Thing
>>>>>> { return (*a)[:] })// The nodes in the linked list of this structure are
>>>>>> 1240 bytes, not that// that's a great number or anything like that, just
>>>>>> saying it's pretty big.// Maybe there'd be something good to get out of
>>>>>> aligning things are cache line// sizes. See TestNodeSize.
>>>>>>
>>>>>> Other things you could do Use a slice for the buffer
>>>>>>
>>>>>> A different approach would be to just have the array in the node,
>>>>>> take a buffer size and then keep a sync.Pool or freelist of slices.
>>>>>> Today's
>>>>>> github.com/google/btree does this but way worse in that it just
>>>>>> keeps a slice of btree.Item. So fine, it's be two objects, the nodes and
>>>>>> their item buffers. Maybe that is the answer but it's pretty lame. My
>>>>>> feeling is once somebody is optimizing a data structure for access
>>>>>> locality
>>>>>> they are trying to optimize as far as they can go.
>>>>>> Ignore or augment the language generics with manual or automatic
>>>>>> specialization
>>>>>>
>>>>>> Today, in performance critical cases, people use a variety of
>>>>>> automatic or manual specialization. There are tools like
>>>>>> https://github.com/cheekybits/genny or
>>>>>> https://github.com/mmatczuk/go_generics. Note that the latter has
>>>>>> been used to good effect in CockroachDB for building specialized
>>>>>> copy-on-write, interval B-trees.
>>>>>>
>>>>>> One answer to this problem might just be that go's generics solution
>>>>>> doesn't solve for the problem of specializing block-based data
>>>>>> structures.
>>>>>> That's not a particularly satisfying answer.
>>>>>> What I might have expected / guess I'm proposing
>>>>>>
>>>>>> Type lists are a thing for utilizing language features which only
>>>>>> apply to certain kinds of types. There should be a way to create a type
>>>>>> list for arrays of types.
>>>>>>
>>>>> As a first pass I would have anticipated that there would be a way to
>>>>>> inform this package of a buffer size maybe drawn from a fixed number of
>>>>>> sizes. For example:
>>>>>>
>>>>>> type BlockSize int
>>>>>> const (
>>>>>> _ BlockSize = 1 << (4*iota)
>>>>>> Block16
>>>>>> Block256
>>>>>> )
>>>>>> // Array here allowstype Array(type T) interface {
>>>>>> type [Block16]T, [Block256]T
>>>>>> }
>>>>>> func New(type T)(blockSize BlockSize) Dequeue(T) {
>>>>>>
>>>>>> Hmm, this function signature would require being able to return
>>>>> different types based on a non-type-parameter, which would require Dequeue
>>>>> to be an interface (I don't see a definition, so I'm not sure)
>>>>>
>>>>> From what I can tell, though, if you make the array-type a
>>>>> type-parameter directly, though, this becomes workable in the current
>>>>> proposal (although rather awkward for users).
>>>>> e.g.
>>>>> https://go2goplay.golang.org/p/UTnElflTH27
>>>>>
>>>>> type ArrayT(type T) interface {
>>>>> type [3]T, [4]T
>>>>> }
>>>>>
>>>>> func NewArray(type T ArrayT(V), V interface{})() T {
>>>>> var v T
>>>>> return v
>>>>> }
>>>>>
>>>>
>>>> Hmm, maybe I was just holding it wrong and the proposal in "What I
>>>> might have expected" already is the proposal.
>>>>
>>>>
>>>>>
>>>>> switch blockSize {
>>>>>> case Block16:
>>>>>> return &(dequeue(T, [Block16]T){ ... })
>>>>>> case Block256:
>>>>>> return &(dequeue(T, [Block16]T){})
>>>>>>
>>>>>> nit: I assume the second type-parameter for this case statement
>>>>> should be Block256.
>>>>>
>>>>>> }
>>>>>> }
>>>>>> type dequeue(type T interface{}, ArrayT Array(T)) struct {
>>>>>> len
>>>>>> }
>>>>>> type node(type T interface{}, ArrayT Array(T)) struct {
>>>>>> left, right *node(T, ArrayT)
>>>>>> rb ringBuf(T, ArrayT)
>>>>>> }
>>>>>> type ringBuf(type T interface{}, ArrayT Array(T)) struct {
>>>>>> head, len int
>>>>>> // buf is known to be an array type with a size of either 16 or 256
>>>>>> so
>>>>>> // I'd expect to be able to interact with this like an array. I
>>>>>> don't think
>>>>>> // that that works today.
>>>>>> buf ArrayT
>>>>>> }
>>>>>>
>>>>>> The above also seems needlessly clunky. I'd prefer if I could just
>>>>>> represent all array types like this:
>>>>>>
>>>>>> type Array(type T) interface {
>>>>>> [...]T
>>>>>> }
>>>>>>
>>>>>> I like that approach to distinguishing between slices and arrays in
>>>>> type-lists.
>>>>> Nit: I think it would still need the type keyword, so it would look
>>>>> like:
>>>>>
>>>>> type Array(type T) interface {
>>>>> type [...]T
>>>>> }
>>>>>
>>>> Yes, definitely, my bad.
>>>>
>>>>>
>>>>> I feel like there must be an interaction with something else that I'm
>>>>> missing, though. Since there is some discussion about limitations with
>>>>> respect to the lack of non-type parameters in the omissions section
>>>>> <https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#omissions>.
>>>>> (although not about arrays in type-list constraints, specifically)
>>>>>
>>>>>> Then I could do the following and everything else should just fall
>>>>>> out.
>>>>>>
>>>>>> func New(type T interface{}, ArrayT Array(T))() Dequeue(T) {
>>>>>> return &(dequeue(T, ArrayT){})
>>>>>> }
>>>>>>
>>>>>> The above feels to me to be compatible with the goals and idioms of
>>>>>> the proposal but I could be missing out on some major complexity. Hope
>>>>>> y'all find this helpful.
>>>>>> Aside
>>>>>>
>>>>>> It would be cool to be able to embed a generic type in another
>>>>>> generics type. I can see why it's annoying because the name of the field
>>>>>> will get totally mangled in the specialization but maybe that's not so
>>>>>> bad?
>>>>>> Maybe you'd actually call the embedded type by its unspecialized type
>>>>>> name
>>>>>> even in the specialized version.
>>>>>>
>>>>>> I would have liked to embed the ringBuf in the node. Given it's not
>>>>>> embedded it's almost not worth abstracting.
>>>>>>
>>>>> I think this is already addressed in the current design
>>>>> <https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#embedding-an-instantiated-interface-type>.
>>>>> You are allowed to directly embed type-parameters, and they have the name
>>>>> of the template argument (rather than its instantiated value).
>>>>>
>>>> Cool, I'll try it out. I found it not compiling with `go tool go2go` in
>>>> my first pass. Maybe I was holding it wrong.
>>>>
>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "golang-nuts" group.
>>>>>> To unsubscribe from this group and stop receiving emails from it,
>>>>>> send an email to golan...@googlegroups.com.
>>>>>> To view this discussion on the web visit
>>>>>> https://groups.google.com/d/msgid/golang-nuts/CA%2BvRuzOYXz1t6CsWLd6gxS4AErRNCwA_ctdSYiu3Mq-YH_TEDA%40mail.gmail.com
>>>>>> <https://groups.google.com/d/msgid/golang-nuts/CA%2BvRuzOYXz1t6CsWLd6gxS4AErRNCwA_ctdSYiu3Mq-YH_TEDA%40mail.gmail.com?utm_medium=email&utm_source=footer>
>>>>>> .
>>>>>>
>>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "golang-nuts" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to golan...@googlegroups.com.
>>>> To view this discussion on the web visit
>>>> https://groups.google.com/d/msgid/golang-nuts/2c712c9d-2a5b-44a9-b783-15585a6654b1o%40googlegroups.com
>>>> <https://groups.google.com/d/msgid/golang-nuts/2c712c9d-2a5b-44a9-b783-15585a6654b1o%40googlegroups.com?utm_medium=email&utm_source=footer>
>>>> .
>>>>
>>> --
>> You received this message because you are subscribed to the Google Groups
>> "golang-nuts" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to golang-nuts+unsubscr...@googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/golang-nuts/24115910-1de9-4ae4-bfc9-c9c8ecdbf539o%40googlegroups.com
>> <https://groups.google.com/d/msgid/golang-nuts/24115910-1de9-4ae4-bfc9-c9c8ecdbf539o%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/CA%2BvRuzNApZExE8TLTY-Ldk9BfGH_kqGP3S-mZVaNfaQVTDrZ5Q%40mail.gmail.com.
