Containers

[clipperhouse]

Containers

[clipperhouse]

Interesting idea. Could be done with a tag, eg, containers:"LinkedList,Set".

[mjibson]

proposal: support Anything<T>. let's take Set as an example. we could have:

// containers:"Set"
type st struct { ... }

which makes

type st_set struct {
    m map[st]bool
}

implemented as a struct because other containers may need extra helper vars, but set could probably just be typedefd to a map directly.

st must be comparable. and a set.go template:

func (ms st_set) Add(x {{.T}}) { ms.m[x] = true }
func (ms st_set) Remove(x {{.T}}) { delete(ms.m[x]) }
func (ms st_set) Contains(x {{.T}}) bool { _, ok := ms.m[x]; return ok }
func (ms st_set) Union(other st_set) st_set {
    n := st_set{m: make(map[{{.T}}]bool)}
    for k := range ms.m {
        n.m[k] = true
    }
    for k := range other.m {
        n.m[k] = true
    }
    return n
}
func (ms st_set) Intersection(other st_set) st_set {
    n := st_set{m: make(map[{{.T}}]bool)}
    for k := range ms.m {
        if _, ok := other.m[k]; ok {
            n.m[k] = true
        }
    }
    return n
}
func (ms st_set) Complement(other st_set) st_set {
    n := st_set{m: make(map[{{.T}}]bool)}
    for k := range ms.m {
        if _, ok := ms.m[k]; !ok {
            n.m[k] = true
        }
    }
    return n
}

[clipperhouse]

Looks great!

[sdboyer]

yeah, i'm thinking about this kind of problem myself - where instead of focusing on attaching methods to existing structs, gen could create type-specific versions of generic datastructures that are known to function well (read: have tests) in a generic context, but are awkward to use, and maybe a bit slower, because the caller has to do type conversions when values return from the datastructure, or when receiving values in an injected closure iterator.

sets were brought up, so i'll point out https://github.com/fatih/set , which i've just started contributing to recently in hopes that it could serve as a datastructure component for my own graph lib, https://github.com/sdboyer/gogl . both of these could benefit from this exact approach. gogl is a long way from being ready for that, but set could be utilized in this way right now.

in this context, gen would need to focus on the ways in which these generic datastructures may need to vary to accommodate the behavior of a particular type. to that end, i've noticed two such considerations thus far:

• Maps cannot use non-hashable datastructures as keys - no slices, maps, or (non-pointer) structs that recursively contain such a structure. Arrays are OK, though.
• Somewhat related to the first, the ability to inject an equality comparison method might be handy.

this is a lot more like C++ templates...at least, in my totally-not-a-C++-guy understanding. but if so, it would mean that the risks of this strategy would be bloating binaries, increasing compile time, and incurring a possible runtime cost to the efficiency of the instruction cache. that risk doesn't seem so bad, though, if the intended use case is generic containers/datastructures, rather than just any ol' thing.

my big question would tend to be, what (if any) information would such a generic datastructure need to provide in order to make it amenable to this sort of generation?

[clipperhouse]

Lots of thoughts here, thanks. I am motivated by the notion of compile-time safety and (hopefully) the perf improvement that comes from avoiding type conversions.

It’s idiomatic in Go to create data structures for interface{}, and then cast them as need be. Which is fine and great in most cases, and the perf penalty is probably small. But if one wants a bit more safety and a bit more perf, that’s the niche I am trying to fill here.

Not to mention style and convenience, which are probably my real motivators. :)

gen does make the trade-off of a bit more work at compile time, as you mention. The Go authors have made this point that generics will require a trade-off, and I am choosing this particular one. My kinda thinking is, let the compiler work hard once and the runtime gets a win on every execution.

Regarding the hashable data structures, I do take care in that regard, see here for example. The rules of equality (and sortability) are well-defined and I exploit them. The types package is a big help.

Regarding your last question, there is not much mystery: all the gen’d code comes from templates, so as a first approximation, you’d take your implementation and substitute something like {{.Type}} where you would otherwise use an interface.

[sdboyer]

It’s idiomatic in Go to create data structures for interface{}, and then cast them as need be. Which is fine and great in most cases, and the perf penalty is probably small. But if one wants a bit more safety and a bit more perf, that’s the niche I am trying to fill here.

Not to mention style and convenience, which are probably my real motivators. :)

yeah, on the perf front, i'm probably nitpicking. i agree that the primary motivation here is style and convenience. the perf case that annoys me a tad is one where, if i'm traversing a large dataset and passing out the value as interface{} to an injected iterator for each item in the set, and the injected iterator performs a very simple operation (e.g., appending the value to a slice), the cost of conversion can become a factor in overall performance. maybe, anyway. i did some quick, probably flawed benchmarks that indicate it's a possible concern.

gen does make the trade-off of a bit more work at compile time, as you mention. The Go authors have made this point that generics will require a trade-off, and I am choosing this particular one. My kinda thinking is, let the compiler work hard once and the runtime gets a win on every execution.

yeah, i pretty much agree. the Go authors have already done so much to improve compile time vs C/C++, we can afford to eat a little bit in order to gain this level of stylistic consistency and convenience. i also don't understand the lower layers well enough to absorb Russ Cox's point about the potential costs to the instruction cache. unless it's no more complicated than there being a cache of finite size, but this leads to more instruction symbols competing for that space.

Regarding the hashable data structures, I do take care in that regard. The rules of equality (and sortability) are well-defined and I exploit them. The types package is a big help.

sweeeeet. clearly i haven't explored your code that much yet :) i also wasn't aware of the types package. seems very handy for meta-work like this.

though i don't actually see a solution in the case you linked to - just that if a struct is not comparable, then methods requiring comparability are not generated (assuming i'm reading correctly). seems like a good first step, but some kind of Equals() method implemented on the struct seems like it could be a gateway to allowing these methods to still be implemented - just using an alternate approach that lets us elaborate on the language spec's definition of comparability. of course, there be dragons, too - just spitballing.

Regarding your last question, there is not much mystery: all the gen’d code comes from templates, so as a first approximation, you’d take your implementation and substitute something like {{.Type}} where you would otherwise use an interface.

yeah, so this is one area where i think it'd be interesting to shift things around a bit. again, having not done this myself before...while text templates for output seems like an excellent starting point, a further goal might be to just manipulate the AST directly and write out from there. not sure it's really designed for that, but go fix has to do its thing somehow.

anyway, the advantage of that approach would be that i can focus on writing generic code and tests for the generic case in my own standalone project. folks can then choose to use the generic pattern directly, or they can use gen to generate type-specific versions. keeps us all loosely coupled.

[sdboyer]

looked into go fix, go/format, etc. a smidge, and it certainly seems feasible to use an AST to dump directly, rather routing through a template.

perhaps a first step would be to convert the template-driven output you currently use to AST-driven output?

[clipperhouse]

Take a crack at it if you like, let me know what you experience.

[sdboyer]

it does sound like fun, will do :)

i may or may not have time to work on it right away, but i'll probably open a PR once i start, just as a way of keeping you apprised.

[clipperhouse]

Implemented: https://github.com/clipperhouse/gen/tree/master/templates/container