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

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

Quote:

BTW, does anyone how to improve an X86?

Are you referring to micro-architecture implementation or ISA?

_________________
Amiga 1200 (rev 1D1, KS 3.2, PiStorm32/RPi CM4/Emu68)
Amiga 500 (rev 6A, ECS, KS 3.2, PiStorm/RPi 4B/Emu68)
Ryzen 9 7950X, DDR5-6000 64 GB RAM, GeForce RTX 4080 16 GB

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.

@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..
~

@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...

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

@Entilzha

Spellchecked & sent yesterday!

check your mailbox.

bye,
eli

ps:
sooooorry

Quote:

PS: Where is your cool avatar?

Quote:

Undergoing spellchecking :)

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

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

Cool!!

Thanks Hyperion!!

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

_________________
Dark Lord Design Wicked Solutions For Damned Problems

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.
It is pitch black. You are likely to be eaten by a grue...

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

@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.
It is pitch black. You are likely to be eaten by a grue...

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

@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.
It is pitch black. You are likely to be eaten by a grue...

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

_________________
Author of the PortablE programming language.
It is pitch black. You are likely to be eaten by a grue...

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

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.
It is pitch black. You are likely to be eaten by a grue...