Tree calculation

[devc1]

If I have 4 level tree, the first 3 levels uses 136 bytes and the last level uses 512 bytes. How much space would the tree take in total ? Is it 136^3 * 512 = 1 287 913 472 Bytes ?

Or is it 136^3 + 512^4 ?
Or 136 + 136^2 + 136^3 + 512^4 ?

[iansjack]

I would have said that it depends upon the size of the pointers you use.

[devc1]

Yeah but what would be the size in that case, in bytes 3 levels 136 bytes last level 512 bytes

1024 entry per tree
64 entries in the last level

[Octocontrabass]

What kind of tree is this?

[devc1]

Something kind of like a page table, If it's going right I think it would solve one of the world biggest software problems.

But let's consider it is a page table, if 3 levels point to another 1024 levels, but the last level has 64 levels. and the 3 levels are 128 bytes in size and the last one is 512 bytes how come the size of the tree be ?

[Octocontrabass]

I still don't understand your tree. How many entries are in the top-level table? How many entries are in each of the second-level tables? What about the third level? The last level?

You need to figure out how many of each table you will have before you can figure out how much space they'll take up.

[iansjack]

As I said before, it all depends upon the size of your pointers. And then, what is the size of the leaves of the tree. Do they consist of bytes, integers, objects of undetermined size, pointers to objects, 1024 character strings, …. ?

It’s trivial to count the number of nodes in the tree (assuming it’s fully populated), but what the leaves represent makes a huge difference.

You are asking “how long is a piece of string?”. The answer is “quite”.

[devc1]

Well you haven't got the answer, the leaves consist of bits !!

I guess I am a genius

The last level consists of pointers, I will tell you later whats the purpose of this tree !!

You should look outside the box to optimize on x86_64 architectures lol that's why I still believe AMD64 is the best architecture yet !!

[devc1]

The total length will be pretty much like this I guess:

136 + 136^2 + 136^3 + (136^3 * 520) = 1,310,571,208 Bytes.

I also came to more compact values so it will be much less I will implement it but it will need some major changes in the kernel, but this will boost its efficiency so much ! How come linux and windows not think of this ?? I think I need to shut up for now maybee ..

[iansjack]

I guess I am a genius

Then you should be able to easily solve this trivial problem.

It sounds as if you are splitting one large bitmap into a number of smaller ones, probably for a physical memory allocator. That's a well-known optization (well, I've been using it for years).

Not thinking that far outside the box.

[iansjack]

The total length will be ... 1,310,571,208 Bytes.

Over 1GB? - that's quite a lot of RAM used for a single data structure.

[devc1]

Think of it, that one gb can represent 256 TB of Memory (in pages) and tons of gbs in 16 byte chunks

And on top of that, we can use it on multiple things.

The 1gb will just be reserved by the kernel, each page will be allocated when needed.

I know you are talking about the bitmap to allocate pages, but it is faster to allocate them using an algorithm out of malloc instead of just filling hundreds of thousands of bitmaps to allocate a chunk of pages don't you think ?

For e.g. in your allocator, you will allocate a 1 GB page per page in a half second, I will allocate 1GB in less than 100 clock cycles that's the difference !

[devc1]

On top of that, this is not a large bitmap split into bitmaps, you are almost half right. This is a special data structure tree that I invented.

This data structure that I thought of will be used on the heap management library, so this will be used on the page allocator, heap allocator, allocations for devices, address space allocations, NUMA will benefit the most of the performance gains.

I'm also aiming to have local and atomic function variants in the heap manager, and seeminly the local (per thread or per processor (like NUMA)) ones will be more than 15 times faster.

The atomic ones will be asynchronous (without spinlock), and in the worst case there will be a spinlock but it will be too quick seemingly

It is a general purpose idea by me, just like the microsoft idea of a n object manager.

I never heard anyone using the optimization that I came out with. everyone uses malloc and keeps searching for chunks and using some sort of cache. Linux splits the pages to power of 2 and keeps searching between chunks.

My allocator will get everything on a blink of an instruction, it won't search for anything ! I thought of that way for a week and came up with the idea !

[Jiyahana]

The first three levels use 136 bytes each, and the last level uses 512 bytes. So, it's the sum of the first three levels 136^3 plus the last level 512.
Total space = 136^3 + 512 = 2,429,760 Bytes