Jump to Content
Register Log in

Bitwise
Blog
Forums
Episode Guide
twitter
We are currently in the process of converting the website to the new design. Some pages, like this one, are still broken. We appreciate your patience.
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
🗩