Using generics

[borosr]

Since Go 1.18 beta is available what do you think about updating the project with generics?
Also, is this project still alive?

[mikekonan]

Just for fun have ported the treemap:
https://github.com/mikekonan/gods-generic

[m-manu]

+1 for this.

[emirpasic]

In the in the roadmap now to move GoDS to generics. This will be a major update, people will still be able to use the old way with previous versoins.

[borosr]

Do you want to keep and support the old, non-generic version (for example) under a v1 package or make a different repository specifically for GoDS generics or just update the go.mod to 1.18 and introduce generics?

[emirpasic]

@borosr most likely it will be a different version, i.e. to indicate a breaking change according to semantic versioning. One will always be able to pull the previous V1 version. So you have another suggestion to keep both in the same repo?

[borosr]

Maybe go submodules would help us. Based on the linked article, if we separate the code into two directories, for example named v1 and v2, probably we can use different go versions in both. What do you think about this idea?

[emirpasic]

Thanks for the input. I will check out the link for sure. The important thing for me is not to force all consumers of GoDS to switch to go 1.18. So the old non-generic stuff should still work on pre 1.18. Also maintaining two different versions at the same time is something I am really not looking forward to, but might be necessary for a few years to come :(

[borosr]

It's fully understandable, I also don't want to force people to switch to newer version. Maintaining two versions, next to each other is a little scary, but I think the performance improvements with the go1.18 may worth it. If you decide to do It, I would be happy to contribute and rewrite the lib to use generics. I gave a try with Red-Black tree, this time go1.18 was in beta and I tried to compare my implementation with the GoDS and the memory allocation significantly reduced with generics. When I have some time, I'm going to run the benchmark again and share it here 🙂

[monitor1379]

I also agree that forcing all GoDS users to use Go 1.18 might not be a good choice, maintaining a new version simultaneously is worth a try.

With full respect to the author @emirpasic , i wrote a version that supports generic programming using Go 1.18 parameterized types, which called YAGoDS - github.com/monitor1379/yagods. Hope it helps and welcome to contribute :D

[emirpasic]

Thank you all for your input and suggestions. I have analyzed a few options from using submodules, subrepos, etc.. Essentially it is tricky to support the same library for different versions of go, i.e. 1.18 (with generics) and versions prior to that. I have come to the conclusion to simply create a new branch, i.e. v2, and then release gods with the v2 tag on github enabling the consumers to make use of v2 via go install, and also still be able to reference the old master or v1 version. On the bright side, this will not cause any breaking changes, on the downside, it will require maintaining two versions in parallel for some time (or simply feature-freezing v1 and only focusing on v2).

I will leave this comment open in case anyone else has better suggestions, in the meantime we will start moving generics into the v2 branch

[thousmile]

+1 for this.

Thanks to the author for his hard work！

[orbitoo]

I'm also very interested in using generics to rewrite this repo but...
Recently I came into a problem that in some data structures with comparisons can't be well-defined in current generics.
For example...

type Comparable interface {
	constraints.Ordered | Comparator // can't support
}

type Comparator interface {
	CompareTo(Comparable) int
}

[chowyu12]

+1

[OladapoAjala]

https://github.com/OladapoAjala/datastructures

I've worked on something similar, I'd be happy to contribute to moving this to generics.

[rubensayshi]

idk why, I guess it's Friday and I was looking for something relaxing ... but I went ahead and transpiled the doublylinkedlist and linkedhashmap to generics...

I stopped after that, realizing this package is quite big and there was noway I was gonna finish doing all of them today (and wondering if it's even useful to do so without coordinating with @emirpasic).

Anyway, here's the result for anyone who wants to fiddle with it a bit without having to go through the same exercise as me: prvbl@8bf64b1

I used comparable for any keys because otherwise I had to put in more effort like @orbitoo already hinted at.
And there's some places where nil was used as return value to indicate no result (for a Get etc), I had to use a helper to produce a zero value for the specified type there, which in some places might require adding a bool to the return to indicate a failure... or maybe the zero value is ok...

As has been demonstrated in numerous blogs and benchmarks online, generics can make for a decent performance gain:

Old:

goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/maps/linkedhashmap
cpu: AMD Ryzen 9 3900 12-Core Processor             
BenchmarkTreeMapGet100-16          	  573139	      1925 ns/op
BenchmarkTreeMapGet1000-16         	   54891	     22120 ns/op
BenchmarkTreeMapGet10000-16        	    4196	    267421 ns/op
BenchmarkTreeMapGet100000-16       	     374	   3207694 ns/op
BenchmarkTreeMapPut100-16          	  237832	      5151 ns/op
BenchmarkTreeMapPut1000-16         	   18453	     64896 ns/op
BenchmarkTreeMapPut10000-16        	    1426	    821032 ns/op
BenchmarkTreeMapPut100000-16       	     147	   8087538 ns/op
BenchmarkTreeMapRemove100-16       	 1575784	       761.3 ns/op
BenchmarkTreeMapRemove1000-16      	  145602	      7500 ns/op
BenchmarkTreeMapRemove10000-16     	    8889	    119766 ns/op
BenchmarkTreeMapRemove100000-16    	       1	47611592470 ns/op
PASS
ok  	github.com/emirpasic/gods/maps/linkedhashmap	69.269s

New:

goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/maps/linkedhashmap
cpu: AMD Ryzen 9 3900 12-Core Processor             
BenchmarkTreeMapGet100-16          	 1740186	       674.2 ns/op
BenchmarkTreeMapGet1000-16         	  147832	      7733 ns/op
BenchmarkTreeMapGet10000-16        	    6301	    162703 ns/op
BenchmarkTreeMapGet100000-16       	     566	   2116937 ns/op
BenchmarkTreeMapPut100-16          	  477369	      2224 ns/op
BenchmarkTreeMapPut1000-16         	   49557	     24588 ns/op
BenchmarkTreeMapPut10000-16        	    3889	    280075 ns/op
BenchmarkTreeMapPut100000-16       	     348	   3495279 ns/op
BenchmarkTreeMapRemove100-16       	 3414817	       353.2 ns/op
BenchmarkTreeMapRemove1000-16      	  292640	      3485 ns/op
BenchmarkTreeMapRemove10000-16     	   26809	     40000 ns/op
BenchmarkTreeMapRemove100000-16    	       1	24960324860 ns/op
PASS
ok  	github.com/emirpasic/gods/maps/linkedhashmap	41.167s

[Seb-C]

Is there any ongoing progress on this? Anything that we (the community) could do to help?

There is still no generic equivalent to this package in the Golang ecosystem (and with such level of quality), and I find myself needing it quite often.

I'd love to provide some help in the implementation, but I find it hard to know where to start or even how to do it without any plan or coordination from the maintainers.

[emirpasicspread]

Hi @Seb-C , my life has been chaotic at the moment due to work and unfortunately I did not have much time to work on it. In December some things are changing and I am looking forward to committing myself to the transition to generics. I just need to pave the road again with some basic structure, then the community can take care of the rest.

[Seb-C]

@emirpasicspread Glad to hear that things will get better for you! Then let's wait, and I'll try to find some time to help whenever the time comes.

[songzhibin97]

Made some migrations, if necessary, I will pr.
https://github.com/songzhibin97/go-baseutils/tree/main/structure

[ugurcsen]

I have implemented generics in this fork https://github.com/ugurcsen/gods-generic and I plan to keep GoDS-Generic in sync with https://github.com/emirpasic/gods. I get better benchmark results against GoDS. You can find benchmark comparison at https://github.com/ugurcsen/gods-generic#testing-and-benchmarking. I hope this helps those who want to use generics.

[andig]

Thanks for porting. I was recently looking for a simple generic queue but couldn‘t find one!
Nitpicking: your gain calculation used the fork as basis. In terms of gain it should be the other way round.

[ugurcsen]

Thanks for porting. I was recently looking for a simple generic queue but couldn‘t find one! Nitpicking: your gain calculation used the fork as basis. In terms of gain it should be the other way round.

I have used f(gain) = (<non-generic>/<generic>)−1 as the formula to calculate gain.
I think if process A works in 150ms and process B works in 50ms, process A 3x faster than process B.
If I use f(gain) = (<non-generic>/<generic>)−1, f(200%) = (150ms/50ms)−1. Am I wrong?

[andig]

Imho B has a gain in speed of 66%. It performs at 33% of the run time of A and A is 200% (or 3x) slower than B.

[luatnd]

I have implemented generics in this fork https://github.com/ugurcsen/gods-generic and I plan to keep GoDS-Generic in sync with https://github.com/emirpasic/gods. I get better benchmark results against GoDS. You can find benchmark comparison at https://github.com/ugurcsen/gods-generic#testing-and-benchmarking. I hope this helps those who want to use generics.

love it, I would like to contribute to it.

[drew-512]

Looks like a lot of interest for generics, plus a great crew and vibes here! Shoutout to @emirpasic and all the others here who have dealt in on this awesome package and who are offing insight into a v2. @rubensayshi, nice work on those investigative benchmarks!

Seems like the consensus is to leave the current repo at v1 (legacy compatibility) and create a v2 with generics.

There also seems to be agreement that generics offer a cleaner approach and a performance boost but comes at the cost of cases where an open-ended comparator func is essential to have. Assuming there is agreement on that, what is the path that gets us both? That is, if open-ended comparators must be supported while generics are the majority of cases, how can we offer both without material penalty? Have the ninja gophers at Google etc already solved this problem -- or what might they recommend?

If we can articulate this, then the hardest work towards a v2 is already done!

[PapaCharlie]

FWIW I think this has been answered with the new cmp package in go 1.21. There is now a stdlib way to ensure types are at least comparable when they need to be and ordered for sorted data structures. I spent the weekend adding the type parameters to the code and am about 2/3 done. I will open the PR soon.

I also definitely agree this should be introduced as a major version without keeping the old non-generic code around. It's still possible to mint new v1 versions if a fix is critical for the non-generic code but attempting to keep both in sync with each other will be a nightmare

[emirpasic]

Thanks to @PapaCharlie this is finally becoming a reality by end of this week in #231
Big kudos to @PapaCharlie - insane progress!

[RyuuyaS]

Hello @emirpasic, can you update more about PR #231. Also big thanks to @PapaCharlie for this.

[Inuart]

on the downside, it will require maintaining two versions in parallel for some time (or simply feature-freezing v1 and only focusing on v2).

Technically, v1 can use the generic code of v2 just to maintain compatibility. Also, right now even go1.19 is no longer supported.

[Seb-C]

Is there a reason for the key to be constrained to comparable for the RBT/treeset/treemap?
Since we explicitly pass a comparator function, I expect that it should use it exclusively and support any.