캐시 크기는 이런 코드로 직접 알아낼 수 있다고 합니다.
우리는 간접적으로 확인해 봅시다.
n * m 2차원 배열에 적당한 숫자를 채우고, 원소들의 합계를 구하는 데 걸린 시간을 구합니다.
세 가지 방법을 사용하고, 더하는 순서는 다음과 같습니다.
rowsum:
===>
===>
===>
colsum:
| | |
| | |
v v v
rndsum:
n * m 번 무작위 원소를 더한다.
측정한 수행시간(초)은 다음과 같습니다:
각 줄은 10회 수행한 평균이고, rndsum의 난수 생성 시간은 제외했습니다.
256 * 256
rowsum: 0.008
colsum: 0.008
rndsum: 0.009
512 * 512
rowsum: 0.034
colsum: 0.037
rndsum: 0.048
1024 * 1024
rowsum: 0.144
colsum: 0.161
rndsum: 0.284
2048 * 2048
rowsum: 0.602
colsum: 0.741
rndsum: 1.329
파이썬으로 작성했기 때문에 배열의 진짜 크기-몇 byte인지-는 알지 못합니다만,
세 프로그램의 시간 복잡도는 O(n*m) 으로 같은데 걸린 시간은 다릅니다.
비슷한 방법으로 행렬을 분할해서 곱셈할 때 분할한 크기에 따라서도 시간이 달라집니다.
위의 결과를 참고하여, 본인 PC의 캐시 크기를 간접적으로 추정하시오.
또는 "캐시 크기를 추정하는" 프로그램을 만들어도 됩니다.
2개의 풀이가 있습니다.
이렇게 하는게 맞는지 모르겠네요;;
32비트에서 파이썬의 숫자 자료형은 기본 GC 영역 12바이트에 2**15 마다 2바이트씩 확장하더군요
리스트의 원소는 4바이트 포인터 같구요
따라서 n x n 행렬의 크기는
n*n*4+n*n*(12+size) + (기타 리스트 컨테이너 및 GC 크기) 로 기타 크기는 무시하고 n*n*(4+12+size)라고 가정했습니다
import timeit,random
def readrow(lst):
n = len(lst)
for i in reversed(range(n)):
for j in reversed(range(n)):
lst[i][j]
def readclm(lst):
n = len(lst)
for i in reversed(range(n)):
for j in reversed(range(n)):
lst[j][i]
for size in range(1,11,2):
typesize = 2+2*size
tmp = (2**15)**size
print(2+2*size, 'byte')
for n in range(32,32*10+1,32):
sp = [[random.randrange(tmp, tmp*(2**15)) for j in range(n)] for i in range(n)]
#print((sp.__sizeof__() + sp[0].__sizeof__()*n + n*n*sp[-1][-1].__sizeof__())/1024, end='\t')
tr = timeit.timeit(stmt = "readrow(sp)", setup = "from __main__ import readrow, sp", number = 100)
tc = timeit.timeit(stmt = "readclm(sp)", setup = "from __main__ import readclm, sp", number = 100)
print(int(n*n*(4+(12+typesize))/1024),f'{tr/tc:.4f}',sep='\t')
print()
4 byte
20 0.9735
80 1.0307
180 0.9847
320 0.9806
500 0.9769
720 0.9683
980 0.9625
1280 0.9355 <<<<<
1620 0.8927
2000 0.8352
8 byte
24 0.9952
96 0.9884
216 0.9830
384 0.9797
600 0.9808
864 0.9646
1176 0.9603
1536 0.9354 <<<<<
1944 0.8831
2400 0.8400
12 byte
28 1.0173
112 1.0084
252 0.9861
448 0.9805
700 0.9833
1008 0.9768
1372 0.9564 <<<<<
1792 0.8968
2268 0.8183
2800 0.7770
16 byte
32 1.0021
128 1.0014
288 0.9879
512 0.9844
800 0.9855
1152 0.9771
1568 0.9471 <<<<<
2048 0.8961
2592 0.8096
3200 0.7724
20 byte
36 0.9723
144 0.9929
324 0.9786
576 0.9656
900 0.9606
1296 0.9537 <<<<<
1764 0.9135 <<<<<
2304 0.8299
2916 0.7793
3600 0.7555
각각의 숫자 자료형 크기마다 매트릭스 크기를 늘려가며, 가로 읽기, 세로 읽기 의 시간 비율 테스트 결과입니다
대략 1500KB 에서 지연이 일어나는게 눈에 뜁니다..
32비트 2코어 3M 캐시 노트북에서 테스트한 결과입니다
L3캐시는 공용으로 쓴다고 하던데, 백그라운드 프로그램들 때문인지 대략 1.5메가 정도 캐시를 활용하는거 같습니다
(최대한 idle 상태에서 파이썬 콘솔만 뛰웠는데 흠...)
참고로 랜덤하게 뽑는 경우는 로스가 심해서 제외했습니다....
가로 세로 읽기는 거의 로스가 없이 0.99가 나오는데 반해 랜덤뽑기는 max ratio가 0.95정도...
캐시 크기 추정
import timeit,random
def readrow(lst):
n = len(lst)
for _ in range(100):
for i in reversed(range(n)):
for j in reversed(range(n)):
lst[i][j]
def readclm(lst):
n = len(lst)
for _ in range(100):
for i in reversed(range(n)):
for j in reversed(range(n)):
lst[j][i]
def test(typesize, n):
size = (typesize-2)//2
element = (2**15)**size
matrix = [[random.randrange(element, element*(2**15)) for j in range(n)] for i in range(n)]
start = timeit.default_timer()
readrow(matrix)
tr = timeit.default_timer() - start
start = timeit.default_timer()
readclm(matrix)
tc = timeit.default_timer() - start
return int(n*n*(4+(12+typesize))/1024), tr/tc
if __name__ == '__main__':
typesize = 16
n = 64
err = 0.01
bottom, top = 0, 1024
while True:
matrix_size, ratio = test(typesize, n)
print(matrix_size, ratio)
if abs(1-ratio/0.9) < err:
print('추정 캐시 크기: {:.2f} MB'.format(matrix_size*1.5/1024))
break
elif ratio > 0.9:
bottom, n = n, (top+n)//2
else:
top, n = n, (bottom+n)//2
128 1.0114874478385838
9248 0.7096249372459973
2888 0.790912998675936
1058 0.9678059458991638
1860 0.927792555675023
2346 0.8503498841339207
2096 0.8911558117786645
추정 캐시 크기: 3.07 MB
비율이 0.9에 수렴하는 크기를 찾아 단순하게 1.5배로 보정했습니다;;;
코어 개수, 32비트 64비트에 따라 다 다르게 나올듯...
이렇게 하는거 맞나요??
import datetime as dt
import random
def rowsum(n, arr):
s = 0
for r in range(n):
for c in range(n):
s += arr[r][c]
#print('-- rowsum done --')
def colsum(n, arr):
s = 0
for c in range(n):
for r in range(n):
s += arr[r][c]
#print('-- colsum done --')
def rndsum(n):
s = 0
for _ in range(n * n):
s = random.randint(0, n*n)
lst = [256, 512, 1024]
for n in lst:
print('\n {0} * {1}'.format(n, n))
arr = [[0 for _ in range(n)] for _ in range(n)]
for r in range(n):
for c in range(n):
arr[r][c] = r * n + c
dsec = 0
for _ in range(10):
startTime = dt.datetime.now()
rowsum(n, arr)
dsec += (dt.datetime.now() - startTime).microseconds
print(f" rowsum: {dsec/10**7}")
dsec = 0
for _ in range(10):
startTime = dt.datetime.now()
colsum(n, arr)
dsec += (dt.datetime.now() - startTime).microseconds
print(f" colsum: {dsec/10**7}")
dsec = 0
for _ in range(10):
startTime = dt.datetime.now()
rndsum(n)
dsec = (dt.datetime.now() - startTime).microseconds
print(f" rndsum: {dsec/10**7}")