-
Notifications
You must be signed in to change notification settings - Fork 1.7k
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
Using generics #179
Comments
Just for fun have ported the treemap: |
1 for this. |
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. |
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? |
@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? |
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? |
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 :( |
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 🙂 |
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 |
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 |
1 for this. Thanks to the author for his hard work! |
I'm also very interested in using generics to rewrite this repo but... type Comparable interface {
constraints.Ordered | Comparator // can't support
}
type Comparator interface {
CompareTo(Comparable) int
} |
1 |
https://github.com/OladapoAjala/datastructures I've worked on something similar, I'd be happy to contribute to moving this to generics. |
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 As has been demonstrated in numerous blogs and benchmarks online, generics can make for a decent performance gain: Old:
New:
|
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. |
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. |
@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. |
Made some migrations, if necessary, I will pr. |
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. |
Thanks for porting. I was recently looking for a simple generic queue but couldn‘t find one! |
I have used |
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. |
love it, I would like to contribute to it. |
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! |
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 |
Thanks to @PapaCharlie this is finally becoming a reality by end of this week in #231 |
Hello @emirpasic, can you update more about PR #231. Also big thanks to @PapaCharlie for this. |
Technically, v1 can use the generic code of v2 just to maintain compatibility. Also, right now even go1.19 is no longer supported. |
Is there a reason for the key to be constrained to |
Since Go 1.18 beta is available what do you think about updating the project with generics?
Also, is this project still alive?
The text was updated successfully, but these errors were encountered: