RLU Hashed Linked List benchmark

[MadPlayer]

• 랜덤함수를 수정했습니다
• 기존 함수들 list 삽입, 삭제, 탐색 코드를 정리했습니다

[MadPlayer]

@kjhnet 교수님 기존 rlu benchlist 에서 thread 수 증가에 따라 성능이 반비례하던 문제가 해결된 것으로 보입니다. cpu affinity 설정을 해주었더니 성능이 크게 증가하지는 않지만 thread 수 증가에 따라 성능이 증가합니다.

SeaBIOS (version 1.13.0-1ubuntu1.1)

iPXE (http://ipxe.org) 00:03.0 CA00 PCI2.10 PnP PMM+7FF8C860+7FECC860 CA00

xv6 e820: 0x0000000000000000-0x000000000009fbff usable e820: 0x000000000009fc00-0x000000000009ffff reserved e820: 0x00000000000f0000-0x00000000000fffff reserved e820: 0x0000000000100000-0x000000007ffdefff usable e820: 0x000000007ffdf000-0x000000007fffffff reserved e820: 0x00000000fffc0000-0x00000000ffffffff reserved Scrubbed memory map: phys: 0x0000000000100000-0x000000007ffdefff ACPI: RSDP 0xf59b0 00014 (v0 BOCHS ) ACPI: RSDT 0x7ffe17ad 00034 (v1 BOCHS BXPCRSDT 00000001 BXPC 00000001) ACPI: FACP 0x7ffe1561 00074 (v1 BOCHS BXPCFACP 00000001 BXPC 00000001) ACPI: DSDT 0x7ffe0040 01521 (v1 BOCHS BXPCDSDT 00000001 BXPC 00000001) ACPI: FACS 0x7ffe0000 00040 ACPI: APIC 0x7ffe15d5 00090 (v1 BOCHS BXPCAPIC 00000001 BXPC 00000001) ACPI: HPET 0x7ffe1665 00038 (v1 BOCHS BXPCHPET 00000001 BXPC 00000001) ACPI: SRAT 0x7ffe169d 00110 (v1 BOCHS BXPCSRAT 00000001 BXPC 00000001) xapic: Using xAPIC LAPIC xapic: Initializing LAPIC (CPU 0) acpi: NUMA node 0: cpus 0 2 mem 0-0x9ffff 0x100000-0x3fffffff acpi: NUMA node 1: cpus 1 3 mem 0x40000000-0x7fffffff acpi: Initializing CPUs acpi: CPU 0 APICID 0 acpi: CPU 1 APICID 1 acpi: CPU 2 APICID 2 acpi: CPU 3 APICID 3 kalloc: pageinfo map has 2 entries using formula (pa+0x7fffffffbffae000) >> 63 acpi: Initializing IOAPICs ioapic: IOAPIC version 0x20 for IRQs 0..23 at 0xfec00000 ioapic: Routing IRQ 4 (rising edge) to APICID 0 hpet: At 0xfed00000, revision 1, period 10 nsec, 3 timers kalloc: 843 MB available in node 0 (metadata: 127 kB, waste: 2.0 kB) kalloc: 949 MB available in node 1 (metadata: 127 kB, waste: 2.0 kB) ioapic: Routing IRQ 1 (rising edge) to APICID 0 initsamp: Unknown manufacturer AcpiOsInstallInterruptHandler not implemented (9, 0xffffffffc01a62a0, 0xffffff000b4e3d48) acpi: Using ACPI for PCI root enumeration pci: Scanning bus 0 e1000: Found 82540EM (desktop) e1000: Waiting for link to come up e1000: Link up at 1000 Mb/s full-duplex acpi: Resolving IRQ of 00:03.00 pin A acpi: PCI device 00:03.00 has ACPI handle _SB.PCI0.S18_ acpi: Found PRT on _SB.PCI0 acpi: Matching entry: PRT{Pin=A Address=0x3ffff SourceIndex=0 Source=_SB.LNKC} acpi: Enabling PCI link _SB.LNKC ioapic: Routing IRQ 11 (level high) to APICID 0 disk_register: memide: 536870912 bytes: memide initdisk: Flashing the filesystem image on the memdisk(s) Writing block 131072 / 131072 Writing blocks ... done! (0 seconds) xapic: Initializing LAPIC (CPU 1) xapic: Initializing LAPIC (CPU 2) xapic: Initializing LAPIC (CPU 3) init complete at Thu Jul 29 4:47:39 2021 $ rlu_benchlist 1 RLU - FINE_GRAINED initialized [max_write_sets = 1] 1 Option is inserted -Nb threads : 1 -Initial size : 32 -Buckets : 1 -Duration : 1000 -Update rate : 200 -range : 64 -Set type : hash-list initialize 32 nodes...done Creating 1 threads... done! join 1 threads... thread 0 end done!

result

Thread 0

add : 2272058

remove : 1775845

contains : 9228325

found : 18589533

================================================= RLU statistics:

t_starts = 22637436 t_finish = 22637436 t_writers = 874989

t_writer_writebacks = 874989 t_writeback_q_iters = 0 a_writeback_q_iters = 0 t_pure_readers = 22637436 t_steals = 0 t_aborts = 0 t_sync_requests = 0 t_sync_and_writeback = 874990

Set size : 35 (expected: 35) Duration : 1000 (ms)

ops : 13276228 (13276228.0 / s)

read ops : 9228325 (9228325.0 / s)

update ops : 4047903 (4047903.0 / s)

benchlist end $ rlu_benchlist 2 RLU - FINE_GRAINED initialized [max_write_sets = 1] 1 Option is inserted -Nb threads : 2 -Initial size : 32 -Buckets : 1 -Duration : 1000 -Update rate : 200 -range : 64 -Set type : hash-list initialize 32 nodes...done Creating 2 threads... done! join 2 threads... thread 0 end thread 1 end done!

result

Thread 0

add : 1619812

remove : 1676935

contains : 6369991

found : 12616230

Thread 1

add : 1826953

remove : 1897648

contains : 7308270

found : 14452196

================================================= RLU statistics:

t_starts = 34099241 t_finish = 34089774 t_writers = 1785366

t_writer_writebacks = 1785366 t_writeback_q_iters = 2108385 a_writeback_q_iters = 1 t_pure_readers = 32759849 t_steals = 59394 t_aborts = 9467 t_sync_requests = 11382 t_sync_and_writeback = 1793182

Set size : 34 (expected: 34) Duration : 1000 (ms)

ops : 20699609 (20699609.0 / s)

read ops : 13678261 (13678261.0 / s)

update ops : 7021348 (7021348.0 / s)

benchlist end $ rlu_benchlist 3 RLU - FINE_GRAINED initialized [max_write_sets = 1] 1 Option is inserted -Nb threads : 3 -Initial size : 32 -Buckets : 1 -Duration : 1000 -Update rate : 200 -range : 64 -Set type : hash-list initialize 32 nodes...done Creating 3 threads... done! join 3 threads... thread 1 end thread 0 end thread 2 end done!

result

Thread 0

add : 1099136

remove : 1165408

contains : 4595680

found : 9164310

Thread 1

add : 1303062

remove : 1373731

contains : 5401265

found : 10714607

Thread 2

add : 1603733

remove : 1661877

contains : 6238016

found : 12327459

================================================= RLU statistics:

t_starts = 40445601 t_finish = 40413323 t_writers = 2522241

t_writer_writebacks = 2522241 t_writeback_q_iters = 5785724 a_writeback_q_iters = 2 t_pure_readers = 36511407 t_steals = 918092 t_aborts = 32278 t_sync_requests = 39371 t_sync_and_writeback = 2549379

Set size : 29 (expected: 29) Duration : 1000 (ms)

ops : 24441908 (24441908.0 / s)

read ops : 16234961 (16234961.0 / s)

update ops : 8206947 (8206947.0 / s)

benchlist end $ rlu_benchlist 4 RLU - FINE_GRAINED initialized [max_write_sets = 1] 1 Option is inserted -Nb threads : 4 -Initial size : 32 -Buckets : 1 -Duration : 1000 -Update rate : 200 -range : 64 -Set type : hash-list initialize 32 nodes...done Creating 4 threads... done! join 4 threads... thread 3 end thread 1 end thread 2 end thread 0 end done!

result

Thread 0

add : 1082395

remove : 1020984

contains : 4371413

found : 8445729

Thread 1

add : 1217989

remove : 1171460

contains : 4861008

found : 9417758

Thread 2

add : 1093543

remove : 1031525

contains : 4403026

found : 8507895

Thread 3

add : 1240125

remove : 1190401

contains : 4929152

found : 9547604

================================================= RLU statistics:

t_starts = 45044409 t_finish = 44967408 t_writers = 3473529

t_writer_writebacks = 3473529 t_writeback_q_iters = 8964056 a_writeback_q_iters = 2 t_pure_readers = 37007737 t_steals = 2997200 t_aborts = 77001 t_sync_requests = 98176 t_sync_and_writeback = 3534355

Set size : 35 (expected: 35) Duration : 1000 (ms)

ops : 27613021 (27613021.0 / s)

read ops : 18564599 (18564599.0 / s)

update ops : 9048422 (9048422.0 / s)

benchlist end $ halt (base) madplayer@madplayer-WS60-7RJ:~/GIT/mvcc-os/os/scalefs (scalefs) ┃ ┗ $

[MadPlayer]

새로 pull request 하겠습니다