FAQ
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.

Search Discussions

  • Dan Kortschak at Jul 24, 2013 at 11:55 pm
    When I run that code (changing Pheromones to [][]float64) it completes
    correctly and uses 29GB.

    --
    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 Lemons at Jul 24, 2013 at 11:57 pm
    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.

    --
    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.
  • Ezequiel Darío Gambaccini at Jul 25, 2013 at 1:19 am
    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.

    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.

    --
    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.
  • Dave Cheney at Jul 25, 2013 at 1:24 am
    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:
    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.
    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.


    --
    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.
    --
    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.
  • Ezequiel Darío Gambaccini at Jul 25, 2013 at 1:29 am
    Silly mistake, I'm downloading the 64 bit version now.
    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:
    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.
    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.


    --
    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.
    --
    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.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJul 24, '13 at 11:36p
activeJul 25, '13 at 1:29a
posts6
users4
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase