Please HELP! Why memory leak


(Dench) #1
// test project main.go
package main

import (
	"fmt"
	"math/big"
	"os"
	"runtime"
	"sync"
	"time"
)

var file, _ = os.Create("20-1.txt")
var round = 1
var input = 3

var size = 1048576
var block = 8192

var s_box = [16][16]int{
	{16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, //0
	{0, 0, 0, 4, 0, 0, 0, 4, 0, 4, 0, 0, 0, 4, 0, 0},  //1
	{0, 0, 0, 2, 0, 4, 2, 0, 0, 0, 2, 0, 2, 2, 2, 0},  //2
	{0, 2, 0, 2, 2, 0, 4, 2, 0, 0, 2, 2, 0, 0, 0, 0},  //3
	{0, 0, 0, 0, 0, 4, 2, 2, 0, 2, 2, 0, 2, 0, 2, 0},  //4
	{0, 2, 0, 0, 2, 0, 0, 0, 0, 2, 2, 2, 4, 2, 0, 0},  //5
	{0, 0, 2, 0, 0, 0, 2, 0, 2, 0, 0, 4, 2, 0, 0, 4},  //6
	{0, 4, 2, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 0, 4},  //7
	{0, 0, 0, 2, 0, 0, 0, 2, 0, 2, 0, 4, 0, 2, 0, 4},  //8
	{0, 0, 2, 0, 4, 0, 2, 0, 2, 0, 0, 0, 2, 0, 4, 0},  //9
	{0, 0, 2, 2, 0, 4, 0, 0, 2, 0, 2, 0, 0, 2, 2, 0},  //A
	{0, 2, 0, 0, 2, 0, 0, 0, 4, 2, 2, 2, 0, 2, 0, 0},  //B
	{0, 0, 2, 0, 0, 4, 0, 2, 2, 2, 2, 0, 0, 0, 2, 0},  //C
	{0, 2, 4, 2, 2, 0, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0},  //D
	{0, 0, 2, 2, 0, 0, 2, 2, 2, 2, 0, 0, 2, 2, 0, 0},  //E
	{0, 4, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4}}  //F

func SPN(a []big.Rat, b [][]big.Rat, base int) {
	for k := base * block; k < (base+1)*block; k++ {
		//fmt.Println(k)
		if a[k].Cmp(big.NewRat(0, 1)) > 0 {
			first := k / 65536
			second := k / 4096 % 16
			third := k / 256 % 16
			fourth := k / 16 % 16
			fifth := k % 16
			for m := 0; m < 16; m++ {
				for n := 0; n < 16; n++ {
					for x := 0; x < 16; x++ {
						for y := 0; y < 16; y++ {
							for z := 0; z < 16; z++ {
								per := int64(s_box[first][m] * s_box[second][n] * s_box[third][x] * s_box[fourth][y] * s_box[fifth][z])
								if per > 0 {
									temp := big.NewRat(per, 1048576)
									temp.Mul(temp, &a[k])
									tt := m*65536 + n*4096 + x*256 + y*16 + z
									var pos [20]int
									for i := 0; i < 20; i++ {
										pos[i] = tt % 2
										tt >>= 1
										tt = 524288*pos[19] + 16384*pos[18] + 512*pos[17] + 16*pos[16] + 262144*pos[15] + 8192*pos[14] + 256*pos[13] + 8*pos[12] + 131072*pos[11] + 4096*pos[10] +
											128*pos[9] + 4*pos[8] + 65536*pos[7] + 2048*pos[6] + 64*pos[5] + 2*pos[4] + 32768*pos[3] + 1024*pos[2] + 32*pos[1] + 1*pos[0]
										b[base][tt].Add(temp, &b[base][tt])
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

func main() {
	start := time.Now()
	runtime.GOMAXPROCS(128)

	var wg sync.WaitGroup
	var a = make([]big.Rat, size)
	var b = make([][]big.Rat, 128)
	var c = make([]big.Rat, size)

	var dot string
	for i := 0; i < 128; i++ {
		b[i] = make([]big.Rat, size)
	}

	a[input].SetFrac(big.NewInt(1), big.NewInt(1))
	change := a[:]

	fmt.Printf("%v", a[input].String())
	for i := 0; i < round; i++ {
		for j := 0; j < 128; j++ {
			//fmt.Printf("%d", j)
			wg.Add(1)
			go func(wg *sync.WaitGroup, j int) {
				//SPN(a, b[j], j)
				SPN(a, b, j)
				for i := block * j; i < block*(j+1); i++ {
					a[i].SetFrac(big.NewInt(0), big.NewInt(1))
				}
				for i := 0; i < size; i++ {
					c[i].Add(&c[i], &b[j][i])
					b[j][i].SetFrac(big.NewInt(0), big.NewInt(1))
				}
				defer wg.Done()
			}(&wg, j)
		}
		wg.Wait()
		change = a
		a = c
		c = change
		/*for i := 0; i < 128; i++ {
			for j := 0; j < size; j++ {
				a[j].Add(&a[j], &b[i][j])
			}
		}
		for i := 0; i < 128; i++ {
			for j := 0; j < size; j++ {
				b[i][j].SetFrac(big.NewInt(0), big.NewInt(1))
			}
		}*/
	}

	for i := 1; i < size; i++ {
		dot = a[i].FloatString(20)
		file.WriteString(dot + "\r\n")
	}
	elapsed := time.Since(start)
	fmt.Printf("\nTook %s\n", elapsed)
}

And the result is


(Ignacio Gómez) #2

What’s your environment (arch, os, etc.)? It simply seems that your asking your OS for more memory than it’s willing to give.


(Jay Ts) #3

I tried running it on my Linux system, which has 8 GB of memory and 8 GB of swap space. It consumed all of the memory and swap space before being killed by the system.


(Ignacio Gómez) #4

I read that as if you were wondering what the error meant, not where all your memory allocations are happening. So I got it to run and profiled it, in case you are interested. This is the result with GOMAXPROCS set to 4:

This one is with the original 128 GOMAXPROCS (which runs some seconds faster, but makes your system almost unusable):

But I don’t think you should be surprised, you are indeed allocating huge amounts of memory. Just take b, which is 128 * 1048576 * 32 (size of big.Rat) = 4294967296 bytes, i.e., over 4 GB alone (or exactly 4 GiB, i.e., 2^32 bytes, as expected).


(Dench) #5

Very very thanks for your useful answer, I actually acquired a lots of knowledge. And I want to know how you know the proportion of memory would use for?


(Dench) #6

Yep, May be the memory is not enough. Because I just have 8GB memory


(Dench) #7

Very very thanks for your useful answer, and specific pictures which all vividly illustrate the problems. I actually acquired a lots of knowledge. And I want to know how you know the proportion of memory would use for?


(Dench) #8

and whether you know how to quickly set b[][] in to (“0/1”), Because the produce of it is the lowest speed in my problem


(Ignacio Gómez) #9

I’m not sure what you are asking. How did I calculate b's size? I only multiplied the size of the array by the size of each array it contains, by the size of the type big.Rat.

Sorry, I don’t get that question either. Could you explain it a little?