immutable icon indicating copy to clipboard operation
immutable copied to clipboard
verified publisher icon benbjohnson

Adds generics

Open laher opened this issue 3 years ago • 4 comments

This fork converts Ben's immutable types with generics. Tests are passing. I haven't really test driven this, but tests are passing...

Notes and open points:

  • List was easier to port. No major changes
  • Map: existing hashing / comparison functions are used, but adjusted
  • Map: exp/constraints.Ordered is used for map keys - this was mainly for the SortedMap support, but it seemed a lot easier to use the same constraint across the board. Note that comparable doesn't support greater-than/less-than, only equality. I'm thinking it might be best to define our own constraint here, for future-proofing as much as anything. I'll aim to implement that on the weekend
  • Map: BREAKING CHANGE: byte slices are no longer supported as hash keys, because of the Ordered constraint. I figure a string(b) conversion is easy enough?
  • I don't know the best way to arrange the go mod. github.com/benjohnson/immutable/v2 seemed appropriate because it's a breaking change.
  • I don't know if there's a nicer way to design the API with further changes - I've gone for the least resistance (there was already a fair bit of resistance, but it fell into place eventually)
    • e.g. could we be using hash/maphash now? I experimented with it, but tests failed
  • WARNING: I did a LOT of repetitive fiddly changes here, and I may have messed up. Honestly I've been away from Go for a year and I just wanted a challenge, so this is the result. If someone is using the original, I'd be grateful for feedback.

laher avatar May 19 '22 11:05 laher

this addresses #22

laher avatar May 19 '22 11:05 laher

Here's the benchmarks for before/after on my Macbook air ... it seems faster, for some things more than others, and there's got to be opportunities to optimize ...

Before (behnbjohnson/master):

goos: darwin
goarch: arm64
pkg: github.com/benbjohnson/immutable
BenchmarkList_Append-8               	1443585	      875.8 ns/op	   3016 B/op	      7 allocs/op
BenchmarkList_Prepend-8              	1774755	      745.6 ns/op	   2521 B/op	      6 allocs/op
BenchmarkList_Set-8                  	2509384	      474.4 ns/op	   2280 B/op	      6 allocs/op
BenchmarkList_Iterator/Forward-8     	192071424	        6.183 ns/op
BenchmarkList_Iterator/Reverse-8     	191412490	        6.270 ns/op
BenchmarkBuiltinSlice_Append/Int-8   	300424912	       11.17 ns/op	     46 B/op	      0 allocs/op
BenchmarkBuiltinSlice_Append/Interface-8         	21144768	       57.92 ns/op	    103 B/op	      0 allocs/op
BenchmarkListBuilder_Append-8                    	33901096	       35.69 ns/op	     24 B/op	      1 allocs/op
BenchmarkListBuilder_Prepend-8                   	40533464	       32.22 ns/op	     24 B/op	      1 allocs/op
BenchmarkListBuilder_Set-8                       	55060813	       21.26 ns/op	      8 B/op	      0 allocs/op
BenchmarkBuiltinMap_Set-8                        	12485011	      114.7 ns/op	     59 B/op	      0 allocs/op
BenchmarkBuiltinMap_Delete-8                     	211588881	        4.982 ns/op	      0 B/op	      0 allocs/op
BenchmarkMap_Set-8                               	1000000	     1022 ns/op	   2192 B/op	      9 allocs/op
BenchmarkMap_Delete-8                            	1000000	     1033 ns/op	   2537 B/op	      8 allocs/op
BenchmarkMap_Iterator/Forward-8                  	100000000	       10.07 ns/op
BenchmarkMapBuilder_Set-8                        	8836093	      161.3 ns/op	    121 B/op	      4 allocs/op
BenchmarkMapBuilder_Delete-8                     	10081660	      111.5 ns/op	     16 B/op	      1 allocs/op
BenchmarkSortedMap_Set-8                         	1000000	     1200 ns/op	   3671 B/op	     13 allocs/op
BenchmarkSortedMap_Delete-8                      	1505666	      796.1 ns/op	   1869 B/op	     10 allocs/op
BenchmarkSortedMap_Iterator/Forward-8            	201211854	        5.942 ns/op
BenchmarkSortedMap_Iterator/Reverse-8            	204755415	        5.861 ns/op
BenchmarkSortedMapBuilder_Set-8                  	7003861	      198.0 ns/op	     95 B/op	      3 allocs/op
BenchmarkSortedMapBuilder_Delete-8               	98165811	       10.84 ns/op	      8 B/op	      1 allocs/op
PASS
ok  	github.com/benbjohnson/immutable	129.150s

After (this PR):

goos: darwin
goarch: arm64
pkg: github.com/benbjohnson/immutable/v2
BenchmarkList_Append-8               	2332291	      627.7 ns/op	   2909 B/op	      6 allocs/op
BenchmarkList_Prepend-8              	2791215	      515.3 ns/op	   2377 B/op	      5 allocs/op
BenchmarkList_Set-8                  	3069924	      389.2 ns/op	   2016 B/op	      5 allocs/op
BenchmarkList_Iterator/Forward-8     	184800504	        6.486 ns/op
BenchmarkList_Iterator/Reverse-8     	186225578	        6.455 ns/op
BenchmarkBuiltinSlice_Append/Int-8   	306112687	        8.559 ns/op	     45 B/op	      0 allocs/op
BenchmarkBuiltinSlice_Append/Interface-8         	17291928	       64.86 ns/op	    101 B/op	      0 allocs/op
BenchmarkListBuilder_Append-8                    	46185006	       30.13 ns/op	      8 B/op	      0 allocs/op
BenchmarkListBuilder_Prepend-8                   	63284326	       26.48 ns/op	      8 B/op	      0 allocs/op
BenchmarkListBuilder_Set-8                       	80127535	       15.00 ns/op	      0 B/op	      0 allocs/op
BenchmarkBuiltinMap_Set-8                        	12888039	      116.1 ns/op	     58 B/op	      0 allocs/op
BenchmarkBuiltinMap_Delete-8                     	212144166	        4.973 ns/op	      0 B/op	      0 allocs/op
BenchmarkMap_Set-8                               	1269951	      969.8 ns/op	   2206 B/op	      7 allocs/op
BenchmarkMap_Delete-8                            	1221712	      990.8 ns/op	   2522 B/op	      8 allocs/op
BenchmarkMap_Iterator/Forward-8                  	122431260	        9.824 ns/op
BenchmarkMapBuilder_Set-8                        	12529899	      138.8 ns/op	     72 B/op	      2 allocs/op
BenchmarkMapBuilder_Delete-8                     	10718444	       96.90 ns/op	      1 B/op	      0 allocs/op
BenchmarkSortedMap_Set-8                         	1525124	      796.2 ns/op	   2670 B/op	     11 allocs/op
BenchmarkSortedMap_Delete-8                      	2183881	      549.2 ns/op	   1335 B/op	     10 allocs/op
BenchmarkSortedMap_Iterator/Forward-8            	233916456	        5.103 ns/op
BenchmarkSortedMap_Iterator/Reverse-8            	241015518	        4.996 ns/op
BenchmarkSortedMapBuilder_Set-8                  	9526461	      146.9 ns/op	     39 B/op	      1 allocs/op
BenchmarkSortedMapBuilder_Delete-8               	440195383	        2.636 ns/op	      0 B/op	      0 allocs/op
PASS
ok  	github.com/benbjohnson/immutable/v2	119.909s

laher avatar May 19 '22 12:05 laher

@laher Thanks for having a go at this. I've been on a Rust project for the last month so I haven't had a chance to dig into the Go generics yet. I took a quick once over and I think it's looking good. I'll probably defer merging this until Go 1.19 is out just so folks have time to move over. The immutable library is still pre-1.0 so I'm not worried about breaking compatibility. I'll just bump this to v0.4.0 once it's merged.

In the meantime, if anyone else gets a chance to try this branch out, please drop your feedback here in this issue.

benbjohnson avatar May 19 '22 23:05 benbjohnson

Cool, makes sense. That also gives me time to ask a few best practice questions on gophers slack #generics channel. For now I have fixed the github action (it was on go1.15 and didn't recognise the [T] syntax), and I removed that v2 module change.

On Fri, May 20, 2022 at 12:00 PM Ben Johnson @.***> wrote:

@laher https://github.com/laher Thanks for having a go at this. I've been on a Rust project for the last month so I haven't had a chance to dig into the Go generics yet. I took a quick once over and I think it's looking good. I'll probably defer merging this until Go 1.19 is out just so folks have time to move over. The immutable library is still pre-1.0 so I'm not worried about breaking compatibility. I'll just bump this to v0.4.0 once it's merged.

In the meantime, if anyone else gets a chance to try this branch out, please drop your feedback here in this issue.

— Reply to this email directly, view it on GitHub https://github.com/benbjohnson/immutable/pull/23#issuecomment-1132309803, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAA6XFIYQF5N2YOM2UHZQ2TVK3IYTANCNFSM5WL5NLFQ . You are receiving this because you were mentioned.Message ID: @.***>

laher avatar May 20 '22 03:05 laher

Hi @benbjohnson. Go 1.19 is out now, so maybe it's time to revisit this?

I had another look through it, it looks pretty straightforward. I've been exploring generics quite a bit more since writing this PR, and this still looks like the natural approach to me. I don't have any improvements to add.

What do you think?

laher avatar Sep 29 '22 01:09 laher

@laher I actually still haven't used generics yet since they were released. I'll take a look over this PR tomorrow and probably merge it in. 👍

benbjohnson avatar Oct 02 '22 14:10 benbjohnson

I gave this a review and it looks pretty straightforward. I'll go ahead and merge and cut a new release. If anyone comes across issues with the API then we can address that in future PRs. Thanks, @laher!

benbjohnson avatar Oct 04 '22 16:10 benbjohnson