Memory efficient implementation of go map?
My use case is to transfer a group of members (integers) over network, so we employ delta encoding and on the receiving end we decode and put the whole list as a map,
map[string]struct{}
for O(1) complexity for membership check.
The problem I am facing is that the actual size of members is only 15MB for 2 Million integers, but the size of the map in heap is 100+MB. Seems like the actual map implementation of Go is not suitable for large maps.
Since it is a client side SDK, I do not want to impact the usable memory much, and there can be multiple such groups that need to be kept in memory for long periods of time--around 1 week.
Is there a better alternative DS in Go for this?
type void struct{}
func ToMap(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
go maps heap-memory
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
|
show 4 more comments
My use case is to transfer a group of members (integers) over network, so we employ delta encoding and on the receiving end we decode and put the whole list as a map,
map[string]struct{}
for O(1) complexity for membership check.
The problem I am facing is that the actual size of members is only 15MB for 2 Million integers, but the size of the map in heap is 100+MB. Seems like the actual map implementation of Go is not suitable for large maps.
Since it is a client side SDK, I do not want to impact the usable memory much, and there can be multiple such groups that need to be kept in memory for long periods of time--around 1 week.
Is there a better alternative DS in Go for this?
type void struct{}
func ToMap(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
go maps heap-memory
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
1
We don't know how you use the map, so it's hard to tell on what / how you could improve your code. One tip you may use is to create a map with capacity provided, if you know how many elements you need to store in it. For that, you may usemake(map[string]struct{}, capacity).
– icza
Nov 20 '18 at 7:47
6
Is there a reason why astringis used for the keys?
– ssemilla
Nov 20 '18 at 8:04
2
"the size of the map in heap is 100+MB" how did you measure this. Are you sure this number is correct? And why on earth are you storing the ints in their string representations? Don't do that.
– Volker
Nov 20 '18 at 8:10
1
The size of thestringrepresentation of anint64may be 4 times bigger than the size ofint64itself. If you do need memory optimized solution, don't convert them tostring. If you do need to handle both integers and strings, consider using 2 maps, one withint64keys and one withstringkeys. And in your example code, you may create the map with capacity, like:out := make(map[int64]void{}, len(v))
– icza
Nov 20 '18 at 8:18
4
As others pointed out, avoid string representations for integers. Useintor, if possible,(u)int32. If the map is still too big, consider a sorted slice and use sort.SearchInts (or SearchStrings if you really can't avoid that) for O(log n) in the worst case.
– Peter
Nov 20 '18 at 8:26
|
show 4 more comments
My use case is to transfer a group of members (integers) over network, so we employ delta encoding and on the receiving end we decode and put the whole list as a map,
map[string]struct{}
for O(1) complexity for membership check.
The problem I am facing is that the actual size of members is only 15MB for 2 Million integers, but the size of the map in heap is 100+MB. Seems like the actual map implementation of Go is not suitable for large maps.
Since it is a client side SDK, I do not want to impact the usable memory much, and there can be multiple such groups that need to be kept in memory for long periods of time--around 1 week.
Is there a better alternative DS in Go for this?
type void struct{}
func ToMap(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
go maps heap-memory
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
My use case is to transfer a group of members (integers) over network, so we employ delta encoding and on the receiving end we decode and put the whole list as a map,
map[string]struct{}
for O(1) complexity for membership check.
The problem I am facing is that the actual size of members is only 15MB for 2 Million integers, but the size of the map in heap is 100+MB. Seems like the actual map implementation of Go is not suitable for large maps.
Since it is a client side SDK, I do not want to impact the usable memory much, and there can be multiple such groups that need to be kept in memory for long periods of time--around 1 week.
Is there a better alternative DS in Go for this?
type void struct{}
func ToMap(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
go maps heap-memory
go maps heap-memory
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
edited Nov 20 '18 at 7:59
zaRRoc
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
asked Nov 20 '18 at 7:43
zaRRoczaRRoc
458
458
1
We don't know how you use the map, so it's hard to tell on what / how you could improve your code. One tip you may use is to create a map with capacity provided, if you know how many elements you need to store in it. For that, you may usemake(map[string]struct{}, capacity).
– icza
Nov 20 '18 at 7:47
6
Is there a reason why astringis used for the keys?
– ssemilla
Nov 20 '18 at 8:04
2
"the size of the map in heap is 100+MB" how did you measure this. Are you sure this number is correct? And why on earth are you storing the ints in their string representations? Don't do that.
– Volker
Nov 20 '18 at 8:10
1
The size of thestringrepresentation of anint64may be 4 times bigger than the size ofint64itself. If you do need memory optimized solution, don't convert them tostring. If you do need to handle both integers and strings, consider using 2 maps, one withint64keys and one withstringkeys. And in your example code, you may create the map with capacity, like:out := make(map[int64]void{}, len(v))
– icza
Nov 20 '18 at 8:18
4
As others pointed out, avoid string representations for integers. Useintor, if possible,(u)int32. If the map is still too big, consider a sorted slice and use sort.SearchInts (or SearchStrings if you really can't avoid that) for O(log n) in the worst case.
– Peter
Nov 20 '18 at 8:26
|
show 4 more comments
1
We don't know how you use the map, so it's hard to tell on what / how you could improve your code. One tip you may use is to create a map with capacity provided, if you know how many elements you need to store in it. For that, you may usemake(map[string]struct{}, capacity).
– icza
Nov 20 '18 at 7:47
6
Is there a reason why astringis used for the keys?
– ssemilla
Nov 20 '18 at 8:04
2
"the size of the map in heap is 100+MB" how did you measure this. Are you sure this number is correct? And why on earth are you storing the ints in their string representations? Don't do that.
– Volker
Nov 20 '18 at 8:10
1
The size of thestringrepresentation of anint64may be 4 times bigger than the size ofint64itself. If you do need memory optimized solution, don't convert them tostring. If you do need to handle both integers and strings, consider using 2 maps, one withint64keys and one withstringkeys. And in your example code, you may create the map with capacity, like:out := make(map[int64]void{}, len(v))
– icza
Nov 20 '18 at 8:18
4
As others pointed out, avoid string representations for integers. Useintor, if possible,(u)int32. If the map is still too big, consider a sorted slice and use sort.SearchInts (or SearchStrings if you really can't avoid that) for O(log n) in the worst case.
– Peter
Nov 20 '18 at 8:26
1
1
We don't know how you use the map, so it's hard to tell on what / how you could improve your code. One tip you may use is to create a map with capacity provided, if you know how many elements you need to store in it. For that, you may use
make(map[string]struct{}, capacity).– icza
Nov 20 '18 at 7:47
We don't know how you use the map, so it's hard to tell on what / how you could improve your code. One tip you may use is to create a map with capacity provided, if you know how many elements you need to store in it. For that, you may use
make(map[string]struct{}, capacity).– icza
Nov 20 '18 at 7:47
6
6
Is there a reason why a
string is used for the keys?– ssemilla
Nov 20 '18 at 8:04
Is there a reason why a
string is used for the keys?– ssemilla
Nov 20 '18 at 8:04
2
2
"the size of the map in heap is 100+MB" how did you measure this. Are you sure this number is correct? And why on earth are you storing the ints in their string representations? Don't do that.
– Volker
Nov 20 '18 at 8:10
"the size of the map in heap is 100+MB" how did you measure this. Are you sure this number is correct? And why on earth are you storing the ints in their string representations? Don't do that.
– Volker
Nov 20 '18 at 8:10
1
1
The size of the
string representation of an int64 may be 4 times bigger than the size of int64 itself. If you do need memory optimized solution, don't convert them to string. If you do need to handle both integers and strings, consider using 2 maps, one with int64 keys and one with string keys. And in your example code, you may create the map with capacity, like: out := make(map[int64]void{}, len(v))– icza
Nov 20 '18 at 8:18
The size of the
string representation of an int64 may be 4 times bigger than the size of int64 itself. If you do need memory optimized solution, don't convert them to string. If you do need to handle both integers and strings, consider using 2 maps, one with int64 keys and one with string keys. And in your example code, you may create the map with capacity, like: out := make(map[int64]void{}, len(v))– icza
Nov 20 '18 at 8:18
4
4
As others pointed out, avoid string representations for integers. Use
int or, if possible, (u)int32. If the map is still too big, consider a sorted slice and use sort.SearchInts (or SearchStrings if you really can't avoid that) for O(log n) in the worst case.– Peter
Nov 20 '18 at 8:26
As others pointed out, avoid string representations for integers. Use
int or, if possible, (u)int32. If the map is still too big, consider a sorted slice and use sort.SearchInts (or SearchStrings if you really can't avoid that) for O(log n) in the worst case.– Peter
Nov 20 '18 at 8:26
|
show 4 more comments
1 Answer
1
active
oldest
votes
This is a more memory efficient form of the map:
type void struct{}
func ToMap(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
Go maps are optimized for integer keys. Optimize the map allocation by giving the exact map size as a hint.
A string has an implicit pointer which would make the garbage collector (gc) follow the pointer every time it scans.
Here is a Go benchmark for 2 million pseudorandom integers:
package main
import (
"math/rand"
"strconv"
"testing"
)
type void struct{}
func ToMap1(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
func ToMap2(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
var benchmarkV = func() int64 {
v := make(int64, 2000000)
for i := range v {
v[i] = rand.Int63()
}
return v
}()
func BenchmarkToMap1(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap1(benchmarkV)
}
}
func BenchmarkToMap2(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap2(benchmarkV)
}
}
Output:
$ go test tomap_test.go -bench=.
BenchmarkToMap1-4 2 973358894 ns/op 235475280 B/op 2076779 allocs/op
BenchmarkToMap2-4 10 188489170 ns/op 44852584 B/op 23 allocs/op
$
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53388332%2fmemory-efficient-implementation-of-go-map%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
This is a more memory efficient form of the map:
type void struct{}
func ToMap(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
Go maps are optimized for integer keys. Optimize the map allocation by giving the exact map size as a hint.
A string has an implicit pointer which would make the garbage collector (gc) follow the pointer every time it scans.
Here is a Go benchmark for 2 million pseudorandom integers:
package main
import (
"math/rand"
"strconv"
"testing"
)
type void struct{}
func ToMap1(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
func ToMap2(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
var benchmarkV = func() int64 {
v := make(int64, 2000000)
for i := range v {
v[i] = rand.Int63()
}
return v
}()
func BenchmarkToMap1(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap1(benchmarkV)
}
}
func BenchmarkToMap2(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap2(benchmarkV)
}
}
Output:
$ go test tomap_test.go -bench=.
BenchmarkToMap1-4 2 973358894 ns/op 235475280 B/op 2076779 allocs/op
BenchmarkToMap2-4 10 188489170 ns/op 44852584 B/op 23 allocs/op
$
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
add a comment |
This is a more memory efficient form of the map:
type void struct{}
func ToMap(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
Go maps are optimized for integer keys. Optimize the map allocation by giving the exact map size as a hint.
A string has an implicit pointer which would make the garbage collector (gc) follow the pointer every time it scans.
Here is a Go benchmark for 2 million pseudorandom integers:
package main
import (
"math/rand"
"strconv"
"testing"
)
type void struct{}
func ToMap1(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
func ToMap2(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
var benchmarkV = func() int64 {
v := make(int64, 2000000)
for i := range v {
v[i] = rand.Int63()
}
return v
}()
func BenchmarkToMap1(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap1(benchmarkV)
}
}
func BenchmarkToMap2(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap2(benchmarkV)
}
}
Output:
$ go test tomap_test.go -bench=.
BenchmarkToMap1-4 2 973358894 ns/op 235475280 B/op 2076779 allocs/op
BenchmarkToMap2-4 10 188489170 ns/op 44852584 B/op 23 allocs/op
$
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
add a comment |
This is a more memory efficient form of the map:
type void struct{}
func ToMap(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
Go maps are optimized for integer keys. Optimize the map allocation by giving the exact map size as a hint.
A string has an implicit pointer which would make the garbage collector (gc) follow the pointer every time it scans.
Here is a Go benchmark for 2 million pseudorandom integers:
package main
import (
"math/rand"
"strconv"
"testing"
)
type void struct{}
func ToMap1(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
func ToMap2(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
var benchmarkV = func() int64 {
v := make(int64, 2000000)
for i := range v {
v[i] = rand.Int63()
}
return v
}()
func BenchmarkToMap1(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap1(benchmarkV)
}
}
func BenchmarkToMap2(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap2(benchmarkV)
}
}
Output:
$ go test tomap_test.go -bench=.
BenchmarkToMap1-4 2 973358894 ns/op 235475280 B/op 2076779 allocs/op
BenchmarkToMap2-4 10 188489170 ns/op 44852584 B/op 23 allocs/op
$
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
This is a more memory efficient form of the map:
type void struct{}
func ToMap(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
Go maps are optimized for integer keys. Optimize the map allocation by giving the exact map size as a hint.
A string has an implicit pointer which would make the garbage collector (gc) follow the pointer every time it scans.
Here is a Go benchmark for 2 million pseudorandom integers:
package main
import (
"math/rand"
"strconv"
"testing"
)
type void struct{}
func ToMap1(v int64) map[string]void {
out := map[string]void{}
for _, i := range v {
out[strconv.Itoa(int(i))] = void{}
}
return out
}
func ToMap2(v int64) map[int64]void {
m := make(map[int64]void, len(v))
for _, i := range v {
m[i] = void{}
}
return m
}
var benchmarkV = func() int64 {
v := make(int64, 2000000)
for i := range v {
v[i] = rand.Int63()
}
return v
}()
func BenchmarkToMap1(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap1(benchmarkV)
}
}
func BenchmarkToMap2(b *testing.B) {
b.ReportAllocs()
b.ResetTimer()
for N := 0; N < b.N; N++ {
ToMap2(benchmarkV)
}
}
Output:
$ go test tomap_test.go -bench=.
BenchmarkToMap1-4 2 973358894 ns/op 235475280 B/op 2076779 allocs/op
BenchmarkToMap2-4 10 188489170 ns/op 44852584 B/op 23 allocs/op
$
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
edited Nov 20 '18 at 19:36
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
answered Nov 20 '18 at 8:30
peterSOpeterSO
95.7k14160177
95.7k14160177
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53388332%2fmemory-efficient-implementation-of-go-map%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
We don't know how you use the map, so it's hard to tell on what / how you could improve your code. One tip you may use is to create a map with capacity provided, if you know how many elements you need to store in it. For that, you may use
make(map[string]struct{}, capacity).– icza
Nov 20 '18 at 7:47
6
Is there a reason why a
stringis used for the keys?– ssemilla
Nov 20 '18 at 8:04
2
"the size of the map in heap is 100+MB" how did you measure this. Are you sure this number is correct? And why on earth are you storing the ints in their string representations? Don't do that.
– Volker
Nov 20 '18 at 8:10
1
The size of the
stringrepresentation of anint64may be 4 times bigger than the size ofint64itself. If you do need memory optimized solution, don't convert them tostring. If you do need to handle both integers and strings, consider using 2 maps, one withint64keys and one withstringkeys. And in your example code, you may create the map with capacity, like:out := make(map[int64]void{}, len(v))– icza
Nov 20 '18 at 8:18
4
As others pointed out, avoid string representations for integers. Use
intor, if possible,(u)int32. If the map is still too big, consider a sorted slice and use sort.SearchInts (or SearchStrings if you really can't avoid that) for O(log n) in the worst case.– Peter
Nov 20 '18 at 8:26