# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# %matplotlib inline
import matplotlib
import numpy as np
from mpmath import mp
import matplotlib.pyplot as plt
from mpl_toolkits.axes_grid1 import host_subplot
import mpl_toolkits.axisartist as AA
import math
import warnings
from ipywidgets import interact, interactive, fixed, interact_manual
plt.rcParams['figure.dpi'] = 180
plt.rcParams['figure.figsize'] = [12.0, 8.0]
plt.rcParams['text.latex.unicode'] = True
plt.rcParams['text.usetex'] = True
plt.rcParams['mathtext.fontset'] = 'stix'
plt.rcParams['font.family'] = 'STIXGeneral'

log_sizes = np.array([i for i in range(1,35)])
sizes = np.array([2**i for i in range(1,35)])


# Register file size is speculative
# Defaults are for AWS EC2 c5.2xlarge, an "Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz"
def init_plot(reg_file=128 * 8, l1=32*1024, l2=1024**2, l3=24 * 1024**2, ram=16 * 1024**3, disk=256 * 1024**3):
    plt.xlabel('Size $\\left[\\log_2 n\\right]$')
    plt.xscale('log')
    plt.xticks(sizes, [str(n) for n in log_sizes])
    plt.gca().xaxis.set_minor_locator(plt.NullLocator())
    
    def mem_line(size, label):
        plt.axvline(size / 32, color='grey', linestyle='--')
        plt.text(size / 32, 100, label)
    
    mem_line(reg_file, "REG")
    mem_line(l1, "L1")
    mem_line(l2, "L2")
    mem_line(l3, "L3")
    mem_line(ram, "RAM")
    mem_line(disk, "DISK")

    plt.yscale('log')
    plt.ylabel('Time $\\left[\\mathtt{sec}\\right]$')


def series(data, color='tab:blue'):
    plt.plot(sizes[:len(data)], data, color=color, marker='.')


# ## Benchmark c5.2xlarge

# + [markdown] toc-hr-collapsed=true toc-nb-collapsed=true
# On AWS EC2 instance type `c5.2xlarge`. Root drive size increased to 256GB and a 64GB swapfile is added. Using `--allocation heap`.
# -

fft = np.fromstring("""
1	0.00000531
2	0.000004477
3	0.000007344
4	0.000009439
5	0.000013781
6	0.000023936
7	0.000042144
8	0.000077292
9	0.000149075
10	0.000309063
11	0.000690227
12	0.001507601
13	0.00330798
14	0.00717378
15	0.002854655
16	0.005344267
17	0.010803624
18	0.022976793
19	0.046437339
20	0.097819326
21	0.203701168
22	0.424807287
23	0.907349772
24	1.858657419
25	4.064888369
26	8.003252785
27	17.67193235
28	34.221835982
""", sep=' ').reshape((-1, 2))[:,1]

fft_sqrt = np.fromstring("""
1	0.000008935
2	0.000038013
3	0.000023374
4	0.000026747
5	0.000029887
6	0.00004039
7	0.000048373
8	0.000072872
9	0.000123616
10	0.000250539
11	0.000507387
12	0.001089775
13	0.002354191
14	0.005096965
15	0.010595209
16	0.022575648
17	0.0473638
18	0.100595503
19	0.211823046
20	0.446282983
21	0.938822169
22	1.9707616190000001
23	4.142269804
24	8.607713068
25	18.171836223
26	37.403999458
""", sep=' ').reshape((-1, 2))[:,1]

fft_rec = np.fromstring("""
1	0.000006159
2	0.000004487
3	0.000006596
4	0.000008758
5	0.000011726
6	0.000026389
7	0.000039159
8	0.000073156
9	0.000148793
10	0.00030885
11	0.000692644
12	0.001506197
13	0.003307426
14	0.00717706
15	0.015458752
16	0.033280211
17	0.071393263
18	0.152663299
19	0.325223417
20	0.691438377
21	1.455103663
22	3.058479201
23	6.4278282
24	13.515026047
""", sep=' ').reshape((-1, 2))[:,1]

init_plot()
series(fft, 'tab:red')
series(fft_sqrt, 'tab:orange')
series(fft_rec, 'tab:blue')

# + [markdown] toc-hr-collapsed=true toc-nb-collapsed=true
# ## Benchmark c5.2xlarge (64MiB RAM)

# + [markdown] toc-hr-collapsed=true toc-nb-collapsed=true
# On AWS EC2 instance type `c5.2xlarge`. Root drive size increased to 256GiB and a 64GiB swapfile is added.
#
# ```
# L1 Instruction-Cache: (32 KiB, 8-way associativity, direct-mapped)
# L1 Data-Cache: (32 KiB, 8-way associativity, direct-mapped)
# L2 Unified-Cache: (1024 KiB, 16-way associativity, direct-mapped)
# L3 Unified-Cache: (24 MiB, 11-way associativity, hash-based-mapping)
# ```
#
# Memory is restricted to 64MiB RAM using cgroups:
#
# ```
# sudo cgcreate -t $USER:$USER -a $USER:$USER -g memory:limited
# # # echo 67108864 > /sys/fs/cgroup/memory/limited/memory.limit_in_bytes
# cgexec -g memory:limited ./fft
# ```
# -

fft_heap = np.fromstring("""
1	0.00034372
2	0.000039486
3	0.000035912
4	0.000037605
5	0.000041504
6	0.000042154
7	0.000055761
8	0.000055802
9	0.000086509
10	0.000104544
11	0.000249147
12	0.000277132
13	0.000917944
14	0.001096818
15	0.00341159
16	0.004738028
17	0.015229078
18	0.020695995
19	0.070773651
20	0.091959886
21	30.928260041
22	40.091185241
23	163.181767742
24	184.1793349
25	832.334289622
""", sep=' ').reshape((-1, 2))[:,1]

fft_mmap = np.fromstring("""
1	0.000327282
2	0.000035651
3	0.000028616
4	0.000040656
5	0.000043662
6	0.000036332
7	0.000054138
8	0.000056564
9	0.000078225
10	0.000108604
11	0.000244958
12	0.000287139
13	0.000859705
14	0.001116579
15	0.003552164
16	0.004715079
17	0.015413409
18	0.021136953
19	0.073038566
20	0.092504724
21	76.226779587
22	68.887253346
23	726.08383654
24	527.209818911
""", sep=' ').reshape((-1, 2))[:,1]

transpose_heap = np.fromstring("""
1	0.000000407
2	0.000000201
3	0.000000508
4	0.000000106
5	0.000000378
6	0.000000184
7	0.000004731
8	0.000000604
9	0.000007464
10	0.000001546
11	0.000031108
12	0.000005326
13	0.00012615
14	0.000028176
15	0.000708114
16	0.000138124
17	0.003178672
18	0.000945967
19	0.015287759
20	0.005595849
21	10.570897667
22	11.281882518
23	48.99322635
24	44.853152764
25	685.421398633
""", sep=' ').reshape((-1, 2))[:,1]

transpose_mmap = np.fromstring("""
1	0.000001035
2	0.000000202
3	0.000000511
4	0.000000152
5	0.000000656
6	0.000000288
7	0.000007064
8	0.000000804
9	0.000011185
10	0.000002899
11	0.000031892
12	0.00000538
13	0.000134255
14	0.000028246
15	0.000710412
16	0.000142058
17	0.003230439
18	0.001012398
19	0.015829714
20	0.005500206
21	10.533343567
22	11.358831156
23	48.803206975
24	44.780711319
25	186.202560067
26	145.289483772
""", sep=' ').reshape((-1, 2))[:,1]

init_plot(ram=64*1024**2)
series(fft_heap, 'tab:red')
series(fft_mmap, 'tab:blue')
series(transpose_heap, 'tab:orange')
series(transpose_mmap, 'tab:cyan')

# ## Benchmark single thread

# c5.2xlarge

fft = np.fromstring("""
1	0.000010837
2	0.00003163
3	0.000021725
4	0.000027168
5	0.000025975
6	0.000034325
7	0.000043394
8	0.000069395
9	0.00013186
10	0.000252507
11	0.000502172
12	0.001078727
13	0.00234277
14	0.00504515
15	0.010528185
16	0.022451856
17	0.046697365
18	0.099328349
19	0.207932491
20	0.444358145
21	0.93529772
22	1.964368904
23	4.132257624
24	8.600371875
25	18.178107202
26	37.357505465
""", sep=' ').reshape((-1, 2))[:,1]

fft_iterative = np.fromstring("""
1	0.000005481
2	0.000004502
3	0.00000692
4	0.000008215
5	0.000011034
6	0.000020269
7	0.000032115
8	0.000056194
9	0.000098589
10	0.000203465
11	0.000447601
12	0.000986478
13	0.002059617
14	0.004453699
15	0.009803471
16	0.022309177
17	0.047588306
18	0.106476312
19	0.26432274
20	0.60108076
21	1.2733614389999999
22	2.688171277
23	5.689161517
24	12.132268398
25	25.850465222
26	55.871878074
""", sep=' ').reshape((-1, 2))[:,1]

fft_depth_first = np.fromstring("""
1	0.000005586
2	0.000005259
3	0.000009514
4	0.000010033
5	0.000013038
6	0.000027076
7	0.000037728
8	0.000062199
9	0.000136259
10	0.000282032
11	0.000628744
12	0.001382235
13	0.003047723
14	0.006714292
15	0.014992353
16	0.033965664
17	0.073531157
18	0.170479579
19	0.409346494
20	1.049937156
21	2.444037146
22	5.505871476
23	12.131428218
24	26.768131456
25	61.079266758
26	133.57830445
""", sep=' ').reshape((-1, 2))[:,1]

fft_recursive = np.fromstring("""
1	0.000005541
2	0.000004514
3	0.000004572
4	0.000005506
5	0.000008072
6	0.000014245
7	0.000031183
8	0.00006486
9	0.000143123
10	0.000324709
11	0.000689698
12	0.00150638
13	0.003293801
14	0.007106039
15	0.01528987
16	0.032758035
17	0.069945614
18	0.148304918
19	0.315367176
20	0.670398505
21	1.417594193
22	2.980605325
23	6.24611864
24	13.096406455
25	27.498664066
26	57.386700655
""", sep=' ').reshape((-1, 2))[:,1]

init_plot()
series(fft, 'black')
series(fft_iterative, 'tab:blue')
series(fft_depth_first, 'tab:orange')
series(fft_recursive, 'tab:pink')
series(fft2_heap, 'tab:cyan')


# + [markdown] toc-hr-collapsed=true toc-nb-collapsed=true
# ## Memory access pattern
# -

def fft_df(values, size, offset, stride, loop):
    if size == 1:
        values += [offset]
    else:
        if stride == loop and loop < 128:
            fft_df(values, size // 2, offset, 2 * stride, 2 * loop)
        else:
            fft_df(values, size // 2, offset, 2 * stride, loop)
            fft_df(values, size // 2, offset + stride, 2 * stride, loop)
        for i in range(size // 2):
            for j in range(loop):
                values += [offset + 2 * i * stride + j]
                values += [offset + 2 * i * stride + j + stride]
    return values


a = fft_df([], 16384, 0, 1, 1)

plt.plot(a, linestyle='', marker='.')

2**15 / 64 / 8

# ## Threads

fft_threads = np.fromstring("""
24	8.602388099
24	4.433958019
24	3.055124852
24	2.35013958
24	2.18961738
24	2.051058217
24	1.933472554
24	1.826348783
24	1.8278633229999999
24	1.837789269
""", sep=' ').reshape((-1, 2))[:,1]

threads = np.array(range(1,20))
plt.xticks(threads, [str(n) for n in threads])
plt.axvline(4, color='grey', linestyle='--')
plt.text(4, 1, 'Cores')
plt.axvline(8, color='grey', linestyle='--')
plt.text(8, 1, 'Hyper threads')
plt.plot(threads[:len(fft_threads)], fft_threads * threads[:len(fft_threads)] / fft_threads[0], marker = '.')

threads[:len(fft_threads)]

# +
2.99


$69.7 billion
# -

104 / 2.3



StarcoderdataJupyterScriptsDedupFiltered