शैडोइंग अभ्यास: Wrote My Own Memory Allocator (and ran DOOM with It) - वीडियो के साथ अंग्रेजी बोलना सीखें
पाठ बनाया जा रहा है...
1
One day I was outside, doing normal human activities like touching grass and listening to birds.
2
When the blazing sun gave me a strange idea.
3
What if I wrote my own malloc?
4
So as soon as I got home I started building.
5
And in this video I'll show you how I wrote my own memory allocator in PUC from scratch
6
and how I used to run a real application.
7
Before we start programming it's important to understand what malloc actually does.
8
The standard malloc function is used to allocate memory dynamically.
9
For example, you can use it to create a dynamic array, precisely known at runtime.
10
But because this is C, there is always some problem with memory hiding somewhere.
11
As you probably know, C doesn't have a built-in garbage collector, so managing memory is the programmer's responsibility.
12
For the allocation, C has a special free function.
13
It takes a pointer to a previously allocated memory block and marks that block as free.
14
So the system can reuse it later.
15
And that means I also need to create my own free function.
16
First I had to choose the names.
17
I remembered the name of my channel and decided to call them podalloc and pod3.
18
But before we continue, let's take a look at how memory allocation actually works.
19
Every process has its own memory space.
20
This space is divided into several zones.
21
At the top we have the stack, which is used for function calls and local variables.
22
Below it we have the heap, which is used exactly for dynamic user data.
23
And this is the part that malloc works with.
24
Below that there are other memory regions used for global variables, program code and other things that are not really important for us right now.
25
In this layout the stack grows downward, while the heap grows upward.
26
And it's better to keep these two zones from overlapping, unless you really want to meet a segmentation fold.
27
Another question is how we can actually use this heap for our needs.
28
We need some way to request memory from the operating system.
29
There are a few ways to do this, but for me the best is MMAP.
30
It works kinda similar to malloc.
31
You tell it how much memory you need and it's returned a pointer to the beginning of that memory region.
32
But the important difference is that malloc reserves memory inside an already existing area.
33
While MMAP asks the iOS for a new memory region of their requested size.
34
Now we can use this to write a simple version of the allocator.
35
To free allocated memory we need to know its size.
36
For that I added a mem block structure with a size field and a data pointer, which points to the beginning of the memory available to the user.
37
In POT-A-LOG we simply call a map to request some memory from the operating system.
38
Then at the beginning of the memory region we place our mem block structure.
39
It works like a header for the allocated block.
40
Later in POT-3 we use this header with monMap monMap does the opposite of mmap.
41
It releases the memory back to the OS.
42
For this to work it needs a pointer to the beginning of the memory region and its size, exactly what we keep in the header.
43
After this we can finally test how it actually works.
44
As you can see I allocated some memory, wrote some text into it and printed it.
45
And works fine!
46
But of course it can't be that easy.
47
Right now this is basically just a wrapper around M-map and Moonmap.
48
The main problem with this approach is time.
49
I wrote a simple test that allocates and frees memory, and then compares it with the malloc from C.
50
As you can see, the difference is really big.
51
My allocator is 435 times slower.
52
It's even slower than me understanding hints.
53
Using this in a real program would seriously slow it down.
54
The reason is M-Map and MoonMap.
55
Every allocation and every free requires a system call.
56
And they are pretty slow.
57
Sometimes they are so slow that you forget why you even call them.
58
To make our allocator faster, we need to reduce the number of M-Map calls as much as possible.
59
A common approach is to call a map once to allocate a large chunk of memory.
60
Usually at least one virtual memory page in your system.
61
If you're wondering what page I'm talking about, here's a quick reminder of what virtual memory is.
62
It's a memory abstraction provided by the operating system.
63
Every process gets its own virtual address space, which is divided into small, fixed-sized parts called pages.
64
The program works with virtual addresses, and the system translates these addresses to real physical memory in RAM.
65
Because of this, variables in different programs can even have the same addresses.
66
But that doesn't mean they are stored in the same place in RAM.
67
Each address just belongs to its own process virtual memory space.
68
So, with a new approach we allocate one big chunk of memory
69
and then filled step by step whenever someone calls for tolog.
70
When this page fills up, we allocate another one.
71
As you can see, in this example we have 8 memory allocations, but only 2 mmap calls.
72
This is one of those cases where the number doesn't matter, but matters how you use it.
73
To implement this I changed the mem block structure a little bit.
74
Now each block works like part of doubly linked list.
75
And I also added a free flag to show whether the block is available for allocation or not.
76
Also because we now use pages, I added a page structure.
77
It works like another list, but instead of linking memory blocks, it links different pages together.
78
This will come in handy later.
79
After this I change the allocator function.
80
Now it searches for a free block with enough space.
81
If it can't find one, we create another memory page.
82
You may notice that if the user asks for only 100 bytes, we allocate an entire page for it.
83
We use a much bigger block.
84
We are just wasting memory.
85
To deal with this, we split the memory block.
86
One part is given to the user and the other part remains free for future allocations.
87
With this new approach I also changed port 3.
88
If we split large memory blocks during allocation, we need to merge them back during their allocation.
89
Then the merged block can be reduced later.
90
And now we only return memory to the system when the whole page becomes free.
91
So this approach reduces main map calls too.
92
Well, let's test this with some allocations.
93
And as you can see it somehow become worse.
94
Now it is 1823 times slower, which doesn't really look like a better solution.
95
Without previous changes, it looks more like a waste of time.
96
But if we look at the number of mMAP calls, it becomes much smaller, so that means the problem is not the system calls.
97
After a bit of investigation, I found that most of the time is spent searching for a free block.
98
More precisely, it takes 99.3% of the total time.
99
On one hand, that's good, because system calls are no longer the main problem.
100
On other hand, now we need some fancy data structure to make it faster.
101
The current version searches through a list of all memory blocks.
102
It has to check each block until it finds a free one.
103
So this takes about 0 and time.
104
Looking at this layout, we can see that free blocks are scattered randomly around the page.
105
At the end of the page, there is also some unused space that has not been allocated yet.
106
What if we move free blocks into a separate list?
107
That's where we can quickly get a free block without searching through all allocated blocks.
108
But there is another problem.
109
We need to find a block with the right size.
110
For example, if we need a block of 100 bytes or more, we may have to skip smaller blocks before finding one that actually fits.
111
This can be fixed too.
112
Instead of using one free list, we create 8 of them.
113
Each list stores memory blocks of a certain size category.
114
When a block is freed, it's added to the appropriate list.
115
The benefit is that this is much faster than the previous approach.
116
Usually programs allocate small chunks of memory, so most allocation will fit into one of those eight categories.
117
Another question is how to do this in code.
118
First I added three list pointers to our structures.
119
Then I added functions for inserting blocks into three lists and removing blocks from them.
120
Now when a new page is created, its first free block is automatically added to the appropriate free list.
121
I also changed how splitting works.
122
Now when we split a block, we remove the original block from the free list, give one part to the user and add the remaining part back to the correct free list.
123
And in pod3 I now use the same insert and remove function to keep all free lists updated.
124
At this point it can already works, but there is always some hidden problem in a low level program.
125
And this time the problem is not even the program itself, it's the machine where the program runs.
126
Right now I can allocate 3 bytes and then 4 bytes.
127
And as you can see the second address is not aligned.
128
On some systems this can cause an error, because some processes don't like unaligned addresses.
129
Also, aligned memory is usually faster to read and write.
130
So, to fix this we need to round up the requested amount of memory.
131
We can do it with simple math, but that would be too slow and I need somehow to justify all the time I spent learning bit operators.
132
This version works much faster.
133
We start by adding this to move the number into the next alignment range.
134
For example, if the number is 12 and the alignment is 8, it becomes 19.
135
When we take that, which is 7, in binary it looks like this, exactly the lowest 3 bits.
136
After that we use the tilde operator to flip the bits and create a mask.
137
Finally we use the end operator to raise the lowest 3 bits.
138
As a result 19 becomes 16, which is perfectly aligned to 8 bytes.
139
Pretty easy, as you can see.
140
So after crawling through the depths of C, we can finally run it.
141
And this version actually works better than all previous ones.
142
Of course it's still not as fast as the original Mylock, but further improvements would be much harder and would probably give us a smaller performance gain.
143
Testing only with benchmarks is boring, so let's see how it works in a real program.
144
For the target I chose Doom.
145
I replaced its original allocation function with my own, added some logs to track memory usage and wrote a small python script to visualize it.
146
After playing for some time, everything worked fine for me, no crashes or anything like that.
147
For me, this was a really interesting project, And I hope you enjoy it too.
148
I recommend you trying to write your own allocator as well.
149
It really helps you understand how memory works and improves your understanding of low-level programming.
150
If you enjoyed this video and want to see more, please subscribe, leave a like and write a comment with your ideas or questions.
151
Thanks for watching!
✨ अनुशंसित वीडियो
C11
27 वाक्य
You are wasting memory
Business EnglishUniversity StudentsWorking Adults
C11
78 वाक्य
How I deploy serverless containers for free
Business EnglishUniversity StudentsWorking Adults
B22
252 वाक्य
Memory is crazy expensive so I made my own…
Business EnglishUniversity StudentsWorking Adults
C11
146 वाक्य
🚫 Java Deadlock Explained: Why Your Code is Stuck 😱 (Beginners Must Watch!)
Business EnglishUniversity StudentsWorking Adults
C11
270 वाक्य
Learning to code: How Pavel Durov learned to program | Lex Fridman Podcast Clips
Business EnglishUniversity StudentsWorking Adults
C11
108 वाक्य
How I Learned Procedural Generation
Business EnglishUniversity StudentsWorking Adults
C13
78 वाक्य
Tragic mistake... Anthropic leaks Claude’s source code
American AccentBusiness EnglishUniversity StudentsWorking Adults
C17
67 वाक्य
8 Most Important System Design Concepts You Should Know
Business EnglishUniversity StudentsWorking Adults
B21
100 वाक्य
The exact moment I destroyed my college career
Business EnglishDaily ConversationUniversity Students
C11
207 वाक्य
How I Made $30,000 Hacking Broken Access Control
Business EnglishUniversity StudentsWorking Adults
B21
207 वाक्य
Go’s Big Mistake
Business EnglishUniversity StudentsWorking Adults
C12
32 वाक्य
Rust in 100 Seconds
American AccentBusiness EnglishUniversity StudentsWorking Adults
इस पाठ की शब्दावली और बोलने के सुझाव
इस वीडियो में शैडोइंग के लिए 151 वाक्य और 1935 शब्द हैं। बोला गया हिस्सा 10:20 लंबा है। वक्ता तेज़ बोलता है, लगभग 187 शब्द प्रति मिनट, इसलिए जुड़ी हुई और कमज़ोर ध्वनियाँ ज़्यादा मिलेंगी। 83% शब्द अंग्रेज़ी के 3,000 सबसे आम शब्दों में से हैं; बाकी शब्द अभ्यास से पहले देख लेना अच्छा रहेगा।
इस वीडियो की मुख्य शब्दावली
वीडियो के 15 सीखने लायक शब्द, उच्चारण और अर्थ के साथ:
| शब्द | उच्चारण | अर्थ |
|---|---|---|
| allocation संज्ञा | /ˌæl.əˈkeɪ.ʃən/ | आवंटन |
| operator संज्ञा | /ˈɑpəˌɹeɪtɚ/ | संचालक |
| dynamic विशेषण | /daɪˈnæm.ɪk/ | क्रियाशील, गतिशील |
| precisely क्रिया विशेषण | /pɹɪˈsaɪs.li/ | यथार्थतः, यथावत् |
| divide क्रिया | /dɪˈvaɪd/ | बांटना |
| stack संज्ञा | /stæk/ | धुआँरा |
| compare क्रिया | /kəmˈpɛɚ/ | तौलना |
| grass संज्ञा | /ɡɹɑːs/ | घास |
| log संज्ञा | /lɔɡ/ | कुंदा, लट्ठा |
| script संज्ञा | /skɹɪpt/ | लिपि, लेखन |
| mask संज्ञा | /mæsk/ | मुखौटा, मास्क |
| usage संज्ञा | /ˈjuːsɪd͡ʒ/ | लौकिकता |
| garbage संज्ञा | /ˈɡɑɹ.bɪd͡ʒ/ | कचरा, कूड़ा |
| scratch क्रिया | /skɹæt͡ʃ/ | नोचना |
| mathematics संज्ञा | /mæθ(.ə)ˈmæt.ɪks/ | गणित, गणित-विधा |
इस वीडियो का व्याकरण
वक्ता जिन संरचनाओं का सबसे अधिक प्रयोग करता है, वीडियो के असली शब्दों के साथ:
| संरचना | वीडियो में |
|---|---|
| Passive voice be + past participle — ज़ोर इस पर कि क्या होता है, न कि कौन करता है | is divided · are stored · is given |
| Relative clauses who / which + उपवाक्य — व्यक्ति या वस्तु के बारे में अतिरिक्त जानकारी | stack, which is · heap, which is · space, which is |
ध्यान देने योग्य उच्चारण
वक्ता 11 बार संक्षिप्त रूपों का प्रयोग करता है, जैसे doesn't, can't, don't। इन्हें वैसे ही छोटा बोलें जैसा आप सुनते हैं।
- “sh” और “zh” की ध्वनियाँ: allocation /ˌæl.əˈkeɪ.ʃən/, benchmark /ˈbɛn(t)ʃmɑːk/, abstraction /æbˈstɹæk.ʃn̩/, visualize /ˈvɪʒuəˌlaɪz/
- लंबे शब्द — बलाघात सही रखें: allocation /ˌæl.əˈkeɪ.ʃən/, operator /ˈɑpəˌɹeɪtɚ/, mathematics /mæθ(.ə)ˈmæt.ɪks/, allocator /ˈæl.ə.keɪ.tə/
इस वीडियो से अभ्यास कैसे करें
- पहले बिना बोले पूरा वीडियो एक बार सुनें और जो शब्द नहीं आते उन्हें लिख लें।
- 0.75× गति से शुरू करें, एक-एक वाक्य की शैडोइंग करें, और सहज लगने पर सामान्य गति पर लौटें।
- अपनी आवाज़ रिकॉर्ड करें और मूल से तुलना करें, ख़ासकर allocation, operator, dynamic जैसे शब्दों पर ध्यान दें।
शैडोइंग तकनीक क्या है?
शैडोइंग (Shadowing) एक विज्ञान-समर्थित भाषा सीखने की तकनीक है जो मूल रूप से पेशेवर दुभाषिया प्रशिक्षण के लिए विकसित की गई थी। विधि सरल लेकिन शक्तिशाली है: आप मूल अंग्रेज़ी ऑडियो सुनते हैं और तुरंत इसे ज़ोर से दोहराते हैं — जैसे वक्ता की छाया 1-2 सेकंड की देरी से। शोध से पता चलता है कि यह उच्चारण सटीकता, स्वर, लय, जुड़ी हुई ध्वनियाँ, सुनने की समझ और बोलने की प्रवाहशीलता में काफ़ी सुधार करता है।