Jump to Content
Register
Forgot your password?
Third-party login
Log in with Discord

Bitwise
Blog
Forums
Episode Guide
twitter
Bitwise»Episode Guide
More Optimization & Clean-Up
References ▼
Wikipedia
Open addressing
[1]17:46
Sean Barrett
A Performance Comparison of Judy to Hash Tables
[2]26:23
Wikipedia
Birthday problem
[3]30:14
Filter mode:
Topics
code generation
data structure
language
memory
optimisation
parsing
performance
profiling
searching
(null topic)
Media
🗹Administrivia
🗪Chat Comment
🏃In-Game
🖮Programming🟉
📖Research
🗩Speech
🎭
🏟
🔗
Link to: current timestamp
Credits
Host
Per Vognsen
Indexer
Matt Mascarenhas
?
?

Keyboard Navigation

Global Keys

[, < / ], > Jump to previous / next episode
W, K, P / S, J, N Jump to previous / next marker
t / T Toggle theatre / SUPERtheatre mode
V Revert filter to original state Y Select link (requires manual Ctrl-c)

Menu toggling

q Quotes r References f Filter y Link c Credits

In-Menu Movement

a
w
s
d
h j k l
←
↑
↓
→

Quotes and References Menus

Enter Jump to timecode

Quotes, References and Credits Menus

o Open URL (in new tab)

Filter Menu

x, Space Toggle category and focus next
X, ShiftSpace Toggle category and focus previous
v Invert topics / media as per focus

Filter and Link Menus

z Toggle filter / linking mode

Credits Menu

Enter Open URL (in new tab)
0:08Recap and set the stage for the day
🗩
0:08Recap and set the stage for the day
🗩
0:08Recap and set the stage for the day
🗩
3:05A few words on the slowness of linearly searching while performing the string interning
🗩
3:05A few words on the slowness of linearly searching while performing the string interning
🗩
3:05A few words on the slowness of linearly searching while performing the string interning
🗩
5:56Run the program on the 6160384-line test3.ion with MSVC's statistical profiler, providing some background on profiling
🏃
🗩
5:56Run the program on the 6160384-line test3.ion with MSVC's statistical profiler, providing some background on profiling
🏃
🗩
5:56Run the program on the 6160384-line test3.ion with MSVC's statistical profiler, providing some background on profiling
🏃
🗩
12:58Check out our performance statistics, to see that _malloc_base() is our biggest consumer of clock cycles
🏃
12:58Check out our performance statistics, to see that _malloc_base() is our biggest consumer of clock cycles
🏃
12:58Check out our performance statistics, to see that _malloc_base() is our biggest consumer of clock cycles
🏃
17:46Review the work implementing an open addressing hash table1 for the string interning
📖
17:46Review the work implementing an open addressing hash table1 for the string interning
📖
17:46Review the work implementing an open addressing hash table1 for the string interning
📖
26:23Recommend Sean Barrett's 'A Performance Comparison of Judy to Hash Tables'2
📖
26:23Recommend Sean Barrett's 'A Performance Comparison of Judy to Hash Tables'2
📖
26:23Recommend Sean Barrett's 'A Performance Comparison of Judy to Hash Tables'2
📖
30:14Review the work on str_hash_range(), and str_intern_range() with a mention of the Birthday Paradox3
📖
30:14Review the work on str_hash_range(), and str_intern_range() with a mention of the Birthday Paradox3
📖
30:14Review the work on str_hash_range(), and str_intern_range() with a mention of the Birthday Paradox3
📖
38:06Review the work using a hash table to optimise the symbol table lookup and type resolution
📖
38:06Review the work using a hash table to optimise the symbol table lookup and type resolution
📖
38:06Review the work using a hash table to optimise the symbol table lookup and type resolution
📖
42:03Re-enable all of ion_compile_file() in addition to the parsing
42:03Re-enable all of ion_compile_file() in addition to the parsing
42:03Re-enable all of ion_compile_file() in addition to the parsing
42:23Run it to find that it doesn't work, and investigate why
🏃
42:23Run it to find that it doesn't work, and investigate why
🏃
42:23Run it to find that it doesn't work, and investigate why
🏃
47:32Revert the uncommitted changes
🗹
47:32Revert the uncommitted changes
🗹
47:32Revert the uncommitted changes
🗹
48:07Regenerate test3.ion and run our program on it performing the full code generation
🏃
48:07Regenerate test3.ion and run our program on it performing the full code generation
🏃
48:07Regenerate test3.ion and run our program on it performing the full code generation
🏃
49:11xanatos387 So in the last stream, at a few points in passing was mentioned some use of randomization in hashing. I didn't understand that - isn't determinism the one thing you need in a hash table? When would you ever use randomization?
🗪
49:11xanatos387 So in the last stream, at a few points in passing was mentioned some use of randomization in hashing. I didn't understand that - isn't determinism the one thing you need in a hash table? When would you ever use randomization?
🗪
49:11xanatos387 So in the last stream, at a few points in passing was mentioned some use of randomization in hashing. I didn't understand that - isn't determinism the one thing you need in a hash table? When would you ever use randomization?
🗪
52:18Consult the profile of the full code generation to see that common_vsprintf() - called by strf() and buf__printf() - is our biggest performance hotspot
🏃
52:18Consult the profile of the full code generation to see that common_vsprintf() - called by strf() and buf__printf() - is our biggest performance hotspot
🏃
52:18Consult the profile of the full code generation to see that common_vsprintf() - called by strf() and buf__printf() - is our biggest performance hotspot
🏃
56:58See that _malloc_base() - also called by strf() - is the second performance hotspot
🏃
56:58See that _malloc_base() - also called by strf() - is the second performance hotspot
🏃
56:58See that _malloc_base() - also called by strf() - is the second performance hotspot
🏃
1:00:22Toggle off the code generation part of ion_compile_file()
1:00:22Toggle off the code generation part of ion_compile_file()
1:00:22Toggle off the code generation part of ion_compile_file()
1:00:31Run it to see that this takes 4 seconds
🏃
1:00:31Run it to see that this takes 4 seconds
🏃
1:00:31Run it to see that this takes 4 seconds
🏃
1:01:23Determine to ignore the C code generation performance for now, and rather remove the temporary allocations for the stretchy buffers
🗩
1:01:23Determine to ignore the C code generation performance for now, and rather remove the temporary allocations for the stretchy buffers
🗩
1:01:23Determine to ignore the C code generation performance for now, and rather remove the temporary allocations for the stretchy buffers
🗩
1:02:47Consult the profile with ion_compile_file() only performing the parsing, to see where buf__grow() creates a performance hotspot
1:02:47Consult the profile with ion_compile_file() only performing the parsing, to see where buf__grow() creates a performance hotspot
1:02:47Consult the profile with ion_compile_file() only performing the parsing, to see where buf__grow() creates a performance hotspot
1:05:24Introduce temp_alloc() to do arena-style memory allocation for buf__grow() to call
1:05:24Introduce temp_alloc() to do arena-style memory allocation for buf__grow() to call
1:05:24Introduce temp_alloc() to do arena-style memory allocation for buf__grow() to call
1:13:29Relieve buf__grow() of calling realloc()
1:13:29Relieve buf__grow() of calling realloc()
1:13:29Relieve buf__grow() of calling realloc()
1:16:07Run it to see that it all actually works
🏃
1:16:07Run it to see that it all actually works
🏃
1:16:07Run it to see that it all actually works
🏃
1:16:56Make buf__grow() call temp_alloc(), and enable the latter to allocate from main memory
1:16:56Make buf__grow() call temp_alloc(), and enable the latter to allocate from main memory
1:16:56Make buf__grow() call temp_alloc(), and enable the latter to allocate from main memory
1:19:02Run it under the profiler, and compare the reports for our two allocators, noting that their total CPU time is similar
🏃
1:19:02Run it under the profiler, and compare the reports for our two allocators, noting that their total CPU time is similar
🏃
1:19:02Run it under the profiler, and compare the reports for our two allocators, noting that their total CPU time is similar
🏃
1:25:50Q&A
🗩
1:25:50Q&A
🗩
1:25:50Q&A
🗩
1:25:57barubro Aren't the profile buckets relative time? Not absolute time?
🗪
1:25:57barubro Aren't the profile buckets relative time? Not absolute time?
🗪
1:25:57barubro Aren't the profile buckets relative time? Not absolute time?
🗪
1:27:38synchronizerman Wait, without malloc how is he allocating memory? Did he make his own memory allocator?
🗪
1:27:38synchronizerman Wait, without malloc how is he allocating memory? Did he make his own memory allocator?
🗪
1:27:38synchronizerman Wait, without malloc how is he allocating memory? Did he make his own memory allocator?
🗪
1:28:38miotatsu stb_sprintf time!
🗪
1:28:38miotatsu stb_sprintf time!
🗪
1:28:38miotatsu stb_sprintf time!
🗪
1:29:27Determine to bug Fabian about the unexpectedly comparable performance of the memory arena allocation vs malloc
1:29:27Determine to bug Fabian about the unexpectedly comparable performance of the memory arena allocation vs malloc
1:29:27Determine to bug Fabian about the unexpectedly comparable performance of the memory arena allocation vs malloc
1:30:26barubro Why not try the other profiler? "Performance wizard"
🗪
1:30:26barubro Why not try the other profiler? "Performance wizard"
🗪
1:30:26barubro Why not try the other profiler? "Performance wizard"
🗪
1:30:48Run it via the "Performance wizard"
🏃
1:30:48Run it via the "Performance wizard"
🏃
1:30:48Run it via the "Performance wizard"
🏃
1:33:26xanatos387 pervognsen Will we do direct code generation now or will we wait on that until we have a CPU to target?
🗪
1:33:26xanatos387 pervognsen Will we do direct code generation now or will we wait on that until we have a CPU to target?
🗪
1:33:26xanatos387 pervognsen Will we do direct code generation now or will we wait on that until we have a CPU to target?
🗪
1:33:48cmdrkroz pervognsen Is the eventual plan to write an Ion compiler in Ion? Reason why I ask is whether this will have the same behavior in the RISC-V itself
🗪
1:33:48cmdrkroz pervognsen Is the eventual plan to write an Ion compiler in Ion? Reason why I ask is whether this will have the same behavior in the RISC-V itself
🗪
1:33:48cmdrkroz pervognsen Is the eventual plan to write an Ion compiler in Ion? Reason why I ask is whether this will have the same behavior in the RISC-V itself
🗪
1:35:01artexx2000 pervognsen Any chance make Ion func call return more than one value in the future when C backend no longer needed?
🗪
1:35:01artexx2000 pervognsen Any chance make Ion func call return more than one value in the future when C backend no longer needed?
🗪
1:35:01artexx2000 pervognsen Any chance make Ion func call return more than one value in the future when C backend no longer needed?
🗪
1:36:55barubro Is the Ion compiler going to be modified to take multiple files? How are you going to handle things like directories for multiple platforms?
🗪
1:36:55barubro Is the Ion compiler going to be modified to take multiple files? How are you going to handle things like directories for multiple platforms?
🗪
1:36:55barubro Is the Ion compiler going to be modified to take multiple files? How are you going to handle things like directories for multiple platforms?
🗪
1:38:10aks_ism If I recall correctly, malloc() does only page table setup, doesn't really allocate any pages. Maybe that's why we are seeing this issue
🗪
1:38:10aks_ism If I recall correctly, malloc() does only page table setup, doesn't really allocate any pages. Maybe that's why we are seeing this issue
🗪
1:38:10aks_ism If I recall correctly, malloc() does only page table setup, doesn't really allocate any pages. Maybe that's why we are seeing this issue
🗪
1:39:45We're coming up to the end, with a glimpse into next week
🗩
1:39:45We're coming up to the end, with a glimpse into next week
🗩
1:39:45We're coming up to the end, with a glimpse into next week
🗩