[go-nuts] Out of memory error when allocating slice of slices on 64 bit machine

On Wed, Jul 24, 2013 at 3:41 PM, wrote:

Hello, I'm implementing the ant system optimization algorithm on the
traveling salesman problem, and to keep track of the pheromones I'm using a
slice of slices.
To diminish memory used, I'm actually creating a jagged matrix, as p(i,j)
= p(j,i) and p(i,i) = 0.
When I try to solve a tsp with 85900 cities, I get an out of memory error.
Acording to what I read from malloc.h, the maximum memory a go program can
allocate are 128gb.
I think my jagged matrix is smaller than that, unless there is something
I'm not considering when calculating the final size.
The size I believe would be (considering a float64 to be 8 bytes long):

(85900 * ((85900/2) - 1)) * 8 / (2**30) = 27,487569302 gb
with float32 it would be :
(85900 * ((85900/2) - 1)) * 4 / (2**30) = 13,743784651 gb

Here is the code to generate the matrix:

func InitializePheromones(size int, base float64) Pheromones {
p := make(Pheromones, size)
for i := 0; i < size; i++ {
p[i] = make([]float64, size-i)
for j := 0; j < len(p[i]); j++ {
p[i][j] = base
}
}
return p
}
At i = 1935 it crashes.
Any ideas would be appreciated ! :)

--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

On 24/07/2013, at 20:57, Kyle Lemons wrote:

It's probably faster and makes the GC happier if you allocate one giant block and subslice that:
func alloc(n int) (v [][]float64) {
base := make([]float64, n*(n+1)/2)
for i := 0; i < n; i++ {
v, base = append(v, base[:n-i:n-i]), base[n-i:] # this uses the new s[i:j:k] syntax at tip
}
return v
}

that being said, you're not considering the amount of memory your slices themselves are using. It will be interesting to hear if your program crashes on the base := line above or during the for loop.

On Wed, Jul 24, 2013 at 3:41 PM, wrote:
Hello, I'm implementing the ant system optimization algorithm on the traveling salesman problem, and to keep track of the pheromones I'm using a slice of slices.
To diminish memory used, I'm actually creating a jagged matrix, as p(i,j) = p(j,i) and p(i,i) = 0.
When I try to solve a tsp with 85900 cities, I get an out of memory error.
Acording to what I read from malloc.h, the maximum memory a go program can allocate are 128gb.
I think my jagged matrix is smaller than that, unless there is something I'm not considering when calculating the final size.
The size I believe would be (considering a float64 to be 8 bytes long):

(85900 * ((85900/2) - 1)) * 8 / (2**30) = 27,487569302 gb
with float32 it would be :
(85900 * ((85900/2) - 1)) * 4 / (2**30) = 13,743784651 gb

Here is the code to generate the matrix:

func InitializePheromones(size int, base float64) Pheromones {
p := make(Pheromones, size)
for i := 0; i < size; i++ {
p[i] = make([]float64, size-i)
for j := 0; j < len(p[i]); j++ {
p[i][j] = base
}
}
return p
}
At i = 1935 it crashes.

Any ideas would be appreciated ! :)

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Kyle, I'm trying your approach, but to no avail.

If I do the following, I get an error of the kind " len argument too large
in make([]float64)".
x := make([]float64, -85900+(85900*85900/2))

Im on go version 1.1.1 darwin/386.

On 24/07/2013, at 20:57, Kyle Lemons wrote:

It's probably faster and makes the GC happier if you allocate one giant
block and subslice that:
func alloc(n int) (v [][]float64) {
base := make([]float64, n*(n+1)/2)
for i := 0; i < n; i++ {
v, base = append(v, base[:n-i:n-i]), base[n-i:] # this uses the new s[i:j:k]
syntax at tip
}
return v
}

that being said, you're not considering the amount of memory your slices
themselves are using. It will be interesting to hear if your program
crashes on the base := line above or during the for loop.


--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

On 24/07/2013, at 22:24, Dave Cheney wrote:

You appear to be using the 32 bit version of Go 1.1.1

On Thu, Jul 25, 2013 at 11:23 AM, Ezequiel Darío Gambaccini
wrote: