Click Here
home features news forums classifieds faqs links search
6093 members 
Amiga Q&A /  Free for All /  Emulation /  Gaming / (Latest Posts)
Login

Nickname

Password

Lost Password?

Don't have an account yet?
Register now!

Support Amigaworld.net
Your support is needed and is appreciated as Amigaworld.net is primarily dependent upon the support of its users.
Donate

Menu
Main sections
Home
Features
News
Forums
Classifieds
Links
Downloads
Extras
OS4 Zone
IRC Network
AmigaWorld Radio
Newsfeed
Top Members
Amiga Dealers
Information
About Us
FAQs
Advertise
Polls
Terms of Service
Search

IRC Channel
Server: irc.amigaworld.net
Ports: 1024,5555, 6665-6669
SSL port: 6697
Channel: #Amigaworld
Channel Policy and Guidelines

Who's Online
10 crawler(s) on-line.
 10 guest(s) on-line.
 0 member(s) on-line.



You are an anonymous user.
Register Now!
 DiscreetFX:  7 mins ago
 freak:  54 mins ago
 Mobileconnect:  1 hr 6 mins ago
 MEGA_RJ_MICAL:  1 hr 22 mins ago
 Cammy:  1 hr 52 mins ago
 Jasper:  1 hr 58 mins ago
 ggw:  2 hrs 15 mins ago
 Hypex:  2 hrs 39 mins ago
 agami:  2 hrs 43 mins ago
 BenMatthew:  2 hrs 44 mins ago

Internet News   Internet News : Memory Management in AmigaOS4.0 Explained
   posted by Rogue on 13-Dec-2005 21:05:03 (16112 reads)
A new article is available on os4.hyperion-entertainment.biz outlining the new and improved memory system on AmigaOS4.0. It describes the method of "slab allocators" and "object caching" that greatly reduce external memory fragmentation while keeping internal fragmentation to a guaranteed minimum and typically provides a constant-time memory allocation.

Read all about it on os4.hyperion-entertainment.biz.
    

STORYID: 2754
Related Links
· More about Internet News
· News by Rogue


Most read story about Internet News
IBM confirms POWER5 server release details

Last news about Internet News
Tom's Hardware run a story on AMIGA
Printer Friendly Page  Send this Story to a Friend

Goto page ( 1 | 2 | 3 | 4 | 5 | 6 )

PosterThread
samo79 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 1:30:58
#81 ]
Elite Member
Joined: 13-Feb-2003
Posts: 3437
From: Italy, Perugia

EntilZha & Rogue

Thanks a lot for your hard work

Hope that finally OS4 is near to completion now


_________________
BACK FOR THE FUTURE

http://www.betatesting.it/backforthefuture

Sam440ep Flex 800 Mhz 1 GB Ram + AmigaOS 4.1 Update 6
AmigaOne XE G3 800 Mhz - 640 MB Ram - Radeon 9200 SE + AmigaOS 4.1 Update 6

 Status: Offline
Profile     Report this post  
A1200 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 1:37:43
#82 ]
Elite Member
Joined: 5-May-2003
Posts: 3086
From: Westhall, UK

I recon with their sudden post increase it is done and they are just waiting for some hardware to sell it with

J/K If it was done, people who have already bought it would be getting their final release CDs...


_________________
Amiga A1200, 3.1 ROMs, Blizzard 1230 MKIV 64MB & FPU, 4GB DoM SSD, Workbench 3.1

 Status: Offline
Profile     Report this post  
Hammer 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 1:41:46
#83 ]
Elite Member
Joined: 9-Mar-2003
Posts: 4270
From: Australia

Quote:
BTW, does anyone how to improve an X86?

Are you referring to micro-architecture implementation or ISA?


_________________
Core i9-9900K, DDR4-3800 32 GB RAM, GeForce RTX 3080 Ti
Ryzen 9 3900X, DDR4-3200 32 GB RAM, GeForce RTX 2080 Ti
Amiga 1200 (rev 1D1, KS 3.2, TF1260, 68060 @ 63 Mhz, 128 MB)
Amiga 500 (rev 6A, KS 3.2, 68K 50Mhz, 12 MB RAM)

 Status: Offline
Profile     Report this post  
miksuh 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 2:23:27
#84 ]
Cult Member
Joined: 10-Mar-2003
Posts: 731
From: Espoo, Finland

Quote:
The first and last letters should be capital, then.


Well maybe

Last edited by miksuh on 15-Dec-2005 at 02:28 AM.
Last edited by miksuh on 15-Dec-2005 at 02:25 AM.

 Status: Offline
Profile     Report this post  
Seer 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 6:49:24
#85 ]
Team Member
Joined: 27-Jun-2003
Posts: 3725
From: The Netherlands

@Atheist

No, no naysaying going on here, but those people, they're looking in, gnashing their teeth, I can hear it.

And you just had to mention it ? Right ? Just hoping a "naysayer" would join in, trolling, so you can keep your own holy crusade going...

Funny isn't it, if a thread doesn't have 1 trollish comment from your "naysayers" you make pretty darn sure to make bait.

Last edited by Seer on 15-Dec-2005 at 06:59 AM.


_________________
~
Everything you say will be misquoted and used against you..
~

 Status: Offline
Profile     Report this post  
AmigaPapst 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 10:21:22
#86 ]
Cult Member
Joined: 2-Nov-2003
Posts: 628
From: Amigavatikan

@EntilZha
Thanks for this great article an your additional explaining.

PS: Where is your cool avatar?


_________________
AmigaOne X1000 1,8 Ghz/2 GB Ram + Radeon 6670 2 GB + AmigaOS4.1
A4000T CyberstormPPC 604e-200Mhz/060/128MB+CybervisionPPC 8MB + AmigaOS4
and anymore other Amigas...

 Status: Offline
Profile     Report this post  
EntilZha 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 12:32:47
#87 ]
OS4 Core Developer
Joined: 27-Aug-2003
Posts: 1679
From: The Jedi Academy, Yavin 4

Quote:
PS: Where is your cool avatar?


Undergoing spellchecking :)


_________________
Thomas, the kernel guy

"I don't have a frigging clue. I'm norwegian" -- Ole-Egil

All opinions expressed are my own and do not necessarily represent those of Hyperion Entertainment

 Status: Offline
Profile     Report this post  
ShowMan 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 12:39:32
#88 ]
Member
Joined: 4-Apr-2005
Posts: 25
From: Milan, Italy

@Entilzha

Spellchecked & sent yesterday!

check your mailbox.

bye,
eli

ps:
sooooorry

 Status: Offline
Profile     Report this post  
hatschi 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 18:03:34
#89 ]
Elite Member
Joined: 1-Dec-2005
Posts: 2328
From: Good old Europe.

Quote:
PS: Where is your cool avatar?


Quote:
Undergoing spellchecking :)


Maybe it would be easier to change your user-name instead of the avatar.

 Status: Offline
Profile     Report this post  
unclecurio 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 15-Dec-2005 22:59:18
#90 ]
Regular Member
Joined: 22-Jan-2003
Posts: 411
From: Edinburgh, Scotland

Interesting stuff. Also had a read of the OS4 "20 Things" section and must say it's very well written and the sort of material that was sorely lacking when I was more closely following the scene. It's the sort of thing that would really make sense to a complete outsider.

It's been many a moon since I posted here but it's nice to drop and see progress is still afoot and at least some of the old names are still here, working on their post-count! Perhaps, one day, I'll return to the fold!

Sorry for ambling a little....


_________________
Folding@Home Team AmigaWorld no: 33424

 Status: Offline
Profile     Report this post  
Amigaguy 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 16-Dec-2005 6:06:06
#91 ]
Member
Joined: 8-Mar-2004
Posts: 31
From: Unknown

Cool!!

Thanks Hyperion!!

 Status: Offline
Profile     Report this post  
TrebleSix 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 16-Dec-2005 10:14:09
#92 ]
Elite Member
Joined: 6-Sep-2004
Posts: 3747
From: Pembrokeshire, Wales

Once again, a great article on a great looking website. Well done guys.
All the best


_________________
Dark Lord Design Wicked Solutions For Damned Problems

 Status: Offline
Profile     Report this post  
ChrisH 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 16-Dec-2005 10:28:02
#93 ]
Elite Member
Joined: 30-Jan-2005
Posts: 6673
From: Unknown

I'm glad to hear that OS4 will have a faster memory allocation system, because the one in OS3 is (in my experience) incredibly slow (so I had to write my own one which runs on top - yuck).

The Hyperion article does very much lack any details about how Slabs/etc are allocated/sized/etc, so I'm going to have to read the original paper about it...


_________________
Author of the PortablE programming language.
I can usually be found on www.Amigans.net (my favourite Amiga forum).
It is pitch black. You are likely to be eaten by a grue...

 Status: Offline
Profile     Report this post  
EntilZha 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 17-Dec-2005 0:37:26
#94 ]
OS4 Core Developer
Joined: 27-Aug-2003
Posts: 1679
From: The Jedi Academy, Yavin 4

Quote:
The Hyperion article does very much lack any details about how Slabs/etc are allocated/sized/etc, so I'm going to have to read the original paper about it...


Yeah, sorry about that, but I had to keep the article short, merly an introduction.... The paper describes the algorithm much better than I could do, anyway,


_________________
Thomas, the kernel guy

"I don't have a frigging clue. I'm norwegian" -- Ole-Egil

All opinions expressed are my own and do not necessarily represent those of Hyperion Entertainment

 Status: Offline
Profile     Report this post  
ChrisH 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 17-Dec-2005 13:04:16
#95 ]
Elite Member
Joined: 30-Jan-2005
Posts: 6673
From: Unknown

@EntilZha:
From a theoretical POV, I am not convinced about one of the major claimed properties of slabs, and that isn't helped by the fact that even the original paper is a little vague on certain implementation points. Perhaps you could answer a few questions for me?

1. It is never stated explicitly, but it seems to be assumed that all slabs contain the same number of chunks - am I right?

2. And is the number of chunks (per slab) small? It seems to be implied (!) that they use 8 chunks per slab.

3. Given all that is true, I can't see how they can claim that (de)allocation is a fast, constant-time operation! While it's obviously true when a suitable slab is available, each slab is pretty small (just 8 chunks), and so will soon be exhausted. Therefore quite frequently a new slab must be allocated (slowly & non-constant time) from the system's underlying "heap" (which is most likely just a linked-list of free memory regions).

Thus slabs simply change the "heap" allocations from a linear O(n) time into O(n/8) time (which is still technically just O(n) time) - not much of an improvement, and certainly not the constant O(1) time that they claimed!

The only time their claim will be true is when allocations & deallocations roughly balance each other - so that the same slabs get re-used. Well, I think most programmers could easily design an allocator which worked well under such forgiving conditions!



The only way to make allocation take less than linear time, when built on top of a linear time allocator, is to have the number of chunks (per slab) roughly proportional to the number of chunks allocated so far. That introduces it's own problems, but it's how I implemented my own super-fast allocator...

However, I do agree that slabs will reduce internal & external fragmentation, and object caching is a good idea (even though it requires special handling in each object (de)allocator).


_________________
Author of the PortablE programming language.
I can usually be found on www.Amigans.net (my favourite Amiga forum).
It is pitch black. You are likely to be eaten by a grue...

 Status: Offline
Profile     Report this post  
EntilZha 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 18-Dec-2005 1:43:28
#96 ]
OS4 Core Developer
Joined: 27-Aug-2003
Posts: 1679
From: The Jedi Academy, Yavin 4

Quote:
1. It is never stated explicitly, but it seems to be assumed that all slabs contain the same number of chunks - am I right?


Only within one cache, since the slab size and the object size is determined at cache creation time... but slab sizes vary from cache to cache, and that also means the number of objects per slab vary... Simplified, the amount of objects per cache is the slab size divided by the object size. And the slab size is chosen in such a way that the internal fragmentation does not exceed 12.5 %

Quote:
And is the number of chunks (per slab) small? It seems to be implied (!) that they use 8 chunks per slab.


What do you mean, chunks ? Objects ?

Anyway, no, there's no such number as 8 chunks per slab.

Assume you have a cache that is supposed to take 32 byte objects. Then each slab is most likely going to be 1 page (4K), and that means each slab can take up 128 objects (which is not quite true, since some memory is used for the slab header - Depending on the amount of objects and internal fragmentation of the slab, the slab header is allocated internal to the slab or external).

So in theory, 128 objects can be allocated until a new slab is necessary.

Quote:
3. Given all that is true, I can't see how they can claim that (de)allocation is a fast, constant-time operation! While it's obviously true when a suitable slab is available, each slab is pretty small (just 8 chunks), and so will soon be exhausted. Therefore quite frequently a new slab must be allocated (slowly & non-constant time) from the system's underlying "heap" (which is most likely just a linked-list of free memory regions).


The frequency is quite low, since there is much movement in and out of slabs.. And most of all, no, 1 and 2 are not true.


Quote:
Thus slabs simply change the "heap" allocations from a linear O(n) time into O(n/8) time (which is still technically just O(n) time) - not much of an improvement, and certainly not the constant O(1) time that they claimed!


Uhm, n what ? If you want to measure the time of an allocation from a list, n is the number of nodes in the list, that must be potentially traversed. O(n) then means that the complexity of the algorithm is linear in the amount of nodes.

However, allocating an object is a constant time algorithm, namely removing the first node from the first slab. Since the caches are greedy and only return memory on demand, the complexity is an amortized constant time.

Quote:
Well, I think most programmers could easily design an allocator which worked well under such forgiving conditions!


Well, you can easily deconstruct any allocator by an appropiate program that does not "play by the rule". It's a proven fact that there is NO ideal memory allocator for every case.

Plus: You claim that allocating new slabs is a linear time operation, which it is not.


_________________
Thomas, the kernel guy

"I don't have a frigging clue. I'm norwegian" -- Ole-Egil

All opinions expressed are my own and do not necessarily represent those of Hyperion Entertainment

 Status: Offline
Profile     Report this post  
ChrisH 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 18-Dec-2005 11:14:07
#97 ]
Elite Member
Joined: 30-Jan-2005
Posts: 6673
From: Unknown

@EntilZha
Thanks for your reply. I wouldn't claim to be a memory expert (being basically self-taught in the bits which interest me), so you'll have to excuse any mistakes which I made (and make:^)

Note that what you refer to as "objects", I am referring to as "chunks" (I.E. "buffers"), since I feel that "object" is a little misleading (it can imply that slabs only contain one type of user-allocated object!). If the object cache was relevant to my questions, then "object" would have been the more helpful term.


Quote:
Only within one cache, since the slab size and the object size is determined at cache creation time... but slab sizes vary from cache to cache, and that also means the number of objects per slab vary... Simplified, the amount of objects per cache is the slab size divided by the object size. And the slab size is chosen in such a way that the internal fragmentation does not exceed 12.5 %


You are of course right about the number of chunks per slab - as I'd forgotten that each slab would be an integer number of pages (doh!), and usually just 1.

So am I right in saying that you ensure you always have at least 8 chunks per slab, to keep internal fragmentation below 12.5% (for objects that match the chunk size)? And that you have many different slabs each with a different chunk size (that are notionally different by about 12.5%) to keep internal fragmentation below 12.5% for variable-sized allocations (e.g. strings)?

If yes to all, then that is quite elegant!


(Refering to my O(n) assertion)
Quote:
Uhm, n what ? If you want to measure the time of an allocation from a list, n is the number of nodes in the list, that must be potentially traversed. O(n) then means that the complexity of the algorithm is linear in the amount of nodes.

However, allocating an object is a constant time algorithm, namely removing the first node from the first slab. Since the caches are greedy and only return memory on demand, the complexity is an amortized constant time.


While your first paragraph is correct, I think that you misunderstood what I was asking. The list I was refering to is NOT the slab's internal list, but the OS's list of free memory regions/pages - which have not yet been allocated to anything.

However, given that slabs are usually just one page, the OS can arrange for single pages to be allocated in constant time. So my original assertion that slab allocation would take O(n) is wrong!

Therefore I agree with you that slabs provide chunk/object allocation in constant time

Well, I'm in a hurry to go, and so can't check what I've said any further, but I think it all makes sense...

Last edited by ChrisH on 18-Dec-2005 at 11:20 AM.


_________________
Author of the PortablE programming language.
I can usually be found on www.Amigans.net (my favourite Amiga forum).
It is pitch black. You are likely to be eaten by a grue...

 Status: Offline
Profile     Report this post  
ChrisH 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 20-Dec-2005 9:57:15
#98 ]
Elite Member
Joined: 30-Jan-2005
Posts: 6673
From: Unknown

@EntilZha
I assume then that everything I've said is correct?


_________________
Author of the PortablE programming language.
I can usually be found on www.Amigans.net (my favourite Amiga forum).
It is pitch black. You are likely to be eaten by a grue...

 Status: Offline
Profile     Report this post  
EntilZha 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 20-Dec-2005 20:13:44
#99 ]
OS4 Core Developer
Joined: 27-Aug-2003
Posts: 1679
From: The Jedi Academy, Yavin 4

Sorry, wasn't following the thread anymore...

Quote:
So am I right in saying that you ensure you always have at least 8 chunks per slab,


No, there's no minimum... The only fixed number is the 12.5 %

Quote:
The list I was refering to is NOT the slab's internal list, but the OS's list of free memory regions/pages - which have not yet been allocated to anything.


Oh, in that case, the complexity would be O(log n) anyway, since it uses a buddy system (at least the final version will, currently, it's a bitmap).

Quote:
However, given that slabs are usually just one page, the OS can arrange for single pages to be allocated in constant time


It goes even further... it you look at the second paper that was linked, you'll see the VMEM resource allocator described in detail. It actually uses object caches to provide a fast way to allocate address space, by providing caches for allocations of different sizes...


_________________
Thomas, the kernel guy

"I don't have a frigging clue. I'm norwegian" -- Ole-Egil

All opinions expressed are my own and do not necessarily represent those of Hyperion Entertainment

 Status: Offline
Profile     Report this post  
ChrisH 
Re: Memory Management in AmigaOS4.0 Explained
Posted on 21-Dec-2005 18:12:32
#100 ]
Elite Member
Joined: 30-Jan-2005
Posts: 6673
From: Unknown

Quote:
No, there's no minimum... The only fixed number is the 12.5%

I'd be interested to know the precise details of how you ensure that, but I guess it'd take too long! Since slabs might be useful for something I want to implement, it seems I'll have to work out the details myself (which is at least an interesting challenge:^)

BTW, the VMEM thing sounds like a neat idea, and I probably ought to investigate it in more detail...


_________________
Author of the PortablE programming language.
I can usually be found on www.Amigans.net (my favourite Amiga forum).
It is pitch black. You are likely to be eaten by a grue...

 Status: Offline
Profile     Report this post  

Goto page ( 1 | 2 | 3 | 4 | 5 | 6 )

[ home ][ about us ][ privacy ] [ forums ][ classifieds ] [ links ][ news archive ] [ link to us ][ user account ]
Copyright (C) 2000 - 2019 Amigaworld.net.
Amigaworld.net was originally founded by David Doyle