|
honey the codewitch wrote: Bottom line is, it's not total RAM usage you need to care about as much as you need to care about allocations per second, vs deallocations per second - your "memory pressure"
Heap allocation/freeing has gained a reputation for being costly. It certainly doesn't have to be, especially if you have a large heap.
If you can afford 25% internal fragmentation, you can do buddy allocation in a dozen instructions or less (including call overhead) - there have been machines providing it as machine instruction. Freeing is even simpler than allocation. To reduce internal fragmentation, you can use fibonacci numbers as block sizes, rather than binary sizes, but buddy combining becomes slightly more complex.
Of course: Every now and then you run out of larger blocks and must combine buddies. But first: The limited number of block sizes means that the free lists each cover a range of sizes - e.g. any request between 257 and 512 units allocate from and free to the same list. If this free list is empty, but bigger blocks are available, cutting one in two is trivial, even if you have to go more than one level up.
Only if all higher lists are empty do you need to combine. If you want to distribute that cost over time, you combine only up to the requested size. That is likely to give you a lot of free blocks of this and smaller sizes for later requests. With binary buddies, combination isn't that costly. If you can require the heap to start at an address that is a multiple of the largest block size, you can really fine tune it, if you work at assembler or high level assembler (i.e. C or C++) level so you can really fine tune it by bit masking addresses directly to find buddies.
If you expect buddy pairing to be a fairly uncommon event (which it usually is), you will free to the head of the free list, which is super cheap. If you expect pairing to be common, you can make a trade: When freeing, scan the free list from the head until you find a larger block address. If you have to combine smaller buddies up to that size "all the time", it suggests that the free list typically is rather short, and so is the search for higher block address. Freeing becomes slightly more costly, but
it keeps the free list sorted, so you can combine all buddies of that size in a single sweep through the list.
It is possible to set up artificial test scenarios where buddy allocation causes a lot of splitting and combining (e.g. oscillating between filling the heap with minimum size blocks, freeing them and filling it with max size blocks). In a real-world load, and you are not starved on total heap size, you won't see much need for combining, and allocate/free is very fast.
The major disadvantage of buddy allocation is the internal fragmentation - for binary buddies: 25% if all block sizes are equally probable - that the probability of requesting e.g. 514 words is as high as that of requesting 512 words. In the stuff I code, 512 is a much more likely size than 514, but YMMV. If your typical allocation size is a binary size plus a small header (which really is a worst case for binary buddy!), consider fibonacci buddy.
If you have super-tight requirements for allocation latency, on the uppermost layer to combine (i.e. half the requested size, with binary buddies), you need not combine them all: Finding the first buddy pair is enough to satisfy the request. You can leave combining the remaining ones at that level for some later time.
If your application causes such a memory pressure that binary buddy allocation takes a noticeable fraction of the CPU power, then I'd like to learn about it! In an embedded environment I'd expect (internal and external) fragmentation in a tiny heap to be a far more significant issue. However: Make sure not to underestimate the internal and external fragmentation of a best or perfect fit allocation scheme! Buddy will probably be better externally and worse internally - but maybe less worse than you'd expect, compared to best/perfect fit algorithms.
|
|
|
|
|
First, I'm talking PC applications. Embedded is a whole different animal, particularly here, since part of what I wrote is fundamentally tied to the presence of virtual memory.
Also you're talking about an unmanaged environment where you can handle your own heap, and you've provided one mechanism for doing it.
.NET uses another. It allocates a huge block as a memory pool. Allocations amount to incrementing a pointer. That's it. You pay for that on the backend through garbage collection.
A scheme just as valid as yours, on a PC with (by today's measure) a reasonable amount of RAM and decent swap.
And whether or not you can do it your way, applications may or may not do it that way. I'd argue most written in C++ probably don't do all that much custom heap stuff at all, just relying on the C and C++ libraries and however those do it.
And then there's the fact that so much of todays code is "managed" (read, garbage collected)
Please keep in mind my position isn't about how you "should" manage the heap. We could argue about that for days.
My position is about the hows and whys of the way it's done on PCs now. This isn't about ideal situations, it's about the present situation, if that makes sense.
Real programmers use butterflies
|
|
|
|
|
honey the codewitch wrote: what I wrote is fundamentally tied to the presence of virtual memory
I'd be happy to learn that connection to virtual memory. I do not immediately see the direct connection between real/virtual memory and heap allocation strategy. Extreme cases may be imagined, as well as in super-fine-tuning, but I have a hard time seeing the connection in the general case - certainly if you claim to be talking about PC applications.
Also you're talking about an unmanaged environment where you can handle your own heap, and you've provided one mechanism for doing it. A managed system also allocates and frees memory from a pool, even if the freeing is a result of a garbage collection process. A managed system may certainly use buddy allocation for providing managed memory.
Also, if you do not trust the management of managed memory to be as efficient as you would like it to be: Feel free to request a huge block of memory at startup, and then do your own, presumably more efficient, memory allocation from that block.
Actually, that is exactly what I did a few years ago when playing around with buddy allocation mechanisms. The code I used for testing/timing my buddy allocation algorithms was written in C#, rather than assembler/C/C++, but they did confirm my ideas that unless you are completely starved on memory space, buddy allocation is a very efficient allocation strategy from a performance point of view.
Maybe you won't be able to trap memory allocations, e.g. if you have no write access to the source code to make adjustments. It takes some sophistication to go into the dotNet memory manager, modifying it to use a different allocation strategy. I never did. But I never rejected a strategy on the grounds that "dotNet doesn't do it that way, and I don't know how to force it to change its ways".
You may complain about the hows and whys of the way it's done on PCs now. This isn't about ideal situations, it's about the present situation, if that makes sense. (Redskin argument: If you don't like it the way it is done in America, go back to where you came from!)
You can handle your own objects. You don't have to point any 'It's his fault!' fingers neither at 'managed memory' nor anything else. If your application needs a well-managed heap, then you allocate a heap, and you manage it well. My theses is that unless you are severely cramped on space in that heap, buddy allocation is one of the most efficient ways to handle that heap of yours.
It might be, even for the underlaying managed memory management system. Probably you won't have any opportunity to affect that. So if your managed memory system is too slow, then you request a memory buffer, and you manage it yourself using better methods.
Your machine may run scores of applications, each of them thinking that they can manage memory better than the common one. So they all allocate huge buffers to do their own administration. Maybe, all things considered, it would have been better relying on the common buffering, with common buffering for all users of the buffer. But maybe you put higher emphasis on 'I did it my way', rather than total system performance.
My position is about the hows and whys of the way it's done on PCs now. This isn't about ideal situations, it's about the present situation, if that makes sense. If you think alternate buddy allocation strategies are unrelated to "the way it's done on PCs now", because 'that's not how they do it', then you're of course welcome to reject the alternatives, even if they would be better.
|
|
|
|
|
You're completely misunderstanding me, even when I went out of my way to make myself clear. There's no where to go from here.
You're talking about a better way to manage memory. I'm not, and never was.
Because I've made my self as clear as I can, I am ending this exchange.
Real programmers use butterflies
|
|
|
|
|
honey the codewitch wrote: I am ending this exchange.
I'm perfectly happy with that!
|
|
|
|
|
And an Android game simulating the landing needs a 21MB download!
Google play - Moon Landing[^]
And that's not an ad for it: it looks like a petty poor game ... 
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
I remember a game like that MANY moons ago, it was a crap app but it was kinda fun at the time.
Never could get the hang of it though.
The less you need, the more you have.
Even a blind squirrel gets a nut...occasionally.
JaxCoder.com
|
|
|
|
|
True fact...
Did you know when you google "apollo 11 mission"...
You use the same amount of storage as they did on the actual mission
Kinda related to what you said. Maybe the same thing.  
And now we waste our time ordering these stickers to put on gas pumps...
why....
Imagine what we could do with that computer storage... of useless information.
|
|
|
|
|
Mike Hankey wrote: They put a man on the moon with 36K of fixed memory and 2K of read/writable memory.
It's not you. I put the blame on JavaScript and front-end frameworks. 
|
|
|
|
|
The less you need, the more you have.
Even a blind squirrel gets a nut...occasionally.
JaxCoder.com
|
|
|
|
|
|
Thanks for the link, fascinating video.
The less you need, the more you have.
Even a blind squirrel gets a nut...occasionally.
JaxCoder.com
|
|
|
|
|
To be fair, you should add the 500 trillion synapsis belonging to the blokes inside the thing.
|
|
|
|
|
I had a hard time deciding what keyboard to buy, and I asked you all in the forum here about it.
My keyboard arrived today, and thanks to the advice here, I think I landed on one I'm really happy with. This Das 5QS is fancy.
I'm not dropping keys when I type anymore! NKRO is cool! I also don't double tap keys anymore - my last keyboard's keys sat high causing a double tap sometimes.
The software is unobtrusive. A little fiddly to use, but easy enough once you get it. It's not required to run the keyboard, but allows you to use all the features you paid for when you bought the thing, including assigning key colors to various things like RAM and CPU usage, or giving yourself a "Photoshop" layout (thinking of making one for VS Code) - there's also an API you can plug into.
I have to say, it's still taking some getting used to typing on a new keyboard, but I like the feel of these Omron Gamma Zulu switches. Apparently they're like a classier version of Cherry MX browns.
The only downside I've found is it's a bit more expensive than most full size RGB lit mechanical keyboards and a lot more expensive than the cheap ones.
I think I prefer it to logitech's gaming keyboards from what I've seen.
Real programmers use butterflies
|
|
|
|
|
LogiTech keyboards don't last, I burn through one in a year to year and a half.
I'm probably like you and spend a LOT of time at the keyboard so a good one is a good investment.
I've had my mechanical keyboard now for about 6 months and it's held up well but I'm constantly fat fingering the damn thing, I'm not a real good typist anyway so can't put all the blame on the keyboard.
The less you need, the more you have.
Even a blind squirrel gets a nut...occasionally.
JaxCoder.com
|
|
|
|
|
I like its style. From what I can hear in other videos, the switches have a nice, satisfying click to them.
All of a sudden, this Logi G510s is lookin' mighty replaceable. 
|
|
|
|
|
If you get one, I really hope you like it. Keyboards are so subjective, and it's a lot of money to spend if you're not totally satisfied. I've only been using this keyboard for about half a day and it's already growing on me. It's that easy to type on. I usually have to spend days adjusting to a new 'board. I don't know what it is about this one. It's just ... smooth.
Real programmers use butterflies
|
|
|
|
|
Are you an affiliate? I didn't look into it, but they list a program on their website. If you're going to recommend it, you might as well get some rewards from them when you are the cause of the sale! 
I've spent time on the site, and it looks like a really nice unit. I may just have to invest in one. I've been using (and spec'ing) Cherry switches and keyboards since my college days - Cherry never made slide rules else I would have used one - and still think highly of the quality. But lately I've been using Omron products and I'm impressed. It's pricey, but I wear out a Logitech at least once a year. The only negative I see is that it's a wired board; I've never much cared for those. Still, I'm thinking it over, real hard! Thanks for the review!
Will Rogers never met me.
|
|
|
|
|
It doesn't matter to me that much, and I don't really want to be plugged into their marketing ecosystem.
I'm only recommending them - which is something I only do if I feel it's a special product - because I feel like being helpful.
That's all I need out of this. If you end up buying one and loving it, great! If not, well it was someone else's recommendation, I swear! 
Real programmers use butterflies
|
|
|
|
|
Okay, I pulled the trigger tonight. My poor little Logitech is getting glitchy again - double and missed key entries - so it's time for it to go. Sadly, I don't have a dishwasher here... Thanks for the tip!
Will Rogers never met me.
|
|
|
|
|
I hope you like it as much as I like mine. It's a joy to use.
Real programmers use butterflies
|
|
|
|
|
I suspect that I will, since I really like real switches. I made about $1000 this week trading options, so I figured I can probably afford a new keyboard. Next week might be different, but at least I'll have a new keyboard to deal with it. Thanks, again, young lady.
Will Rogers never met me.
|
|
|
|
|
Hope you enjoy it! I've had my Das Model S Professional for like... 7-10(?) years or so and I don't feel like I'll need to replace it anytime soon. Still going strong.
|
|
|
|
|
I am using an old IBM KB-7953 keyboard (with a PS-2 -> USB adapter) from 1998 and it still works perfectly -- great keyboard feel. The texture has worn off the most-used keys, but the letting is still sharp. I planned ahead and set a few aside in case this one wears out ... doesn't look like that will happen. IBM really grokked typing back then.
|
|
|
|
|
I'd probably still have dropped keys with it because of the way I type. NKRO has changed my life.
Anything over PS/2 isn't going to have it.
Real programmers use butterflies
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
