Tree calculation

Programming, for all ages and all languages.
Post Reply
devc1
Member
Member
Posts: 439
Joined: Fri Feb 11, 2022 4:55 am
Location: behind the keyboard

Tree calculation

Post by 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 ?
User avatar
iansjack
Member
Member
Posts: 4671
Joined: Sat Mar 31, 2012 3:07 am
Location: Chichester, UK

Re: Tree calculation

Post by iansjack »

I would have said that it depends upon the size of the pointers you use.
devc1
Member
Member
Posts: 439
Joined: Fri Feb 11, 2022 4:55 am
Location: behind the keyboard

Re: Tree calculation

Post by 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
Member
Member
Posts: 5452
Joined: Mon Mar 25, 2013 7:01 pm

Re: Tree calculation

Post by Octocontrabass »

What kind of tree is this?
devc1
Member
Member
Posts: 439
Joined: Fri Feb 11, 2022 4:55 am
Location: behind the keyboard

Re: Tree calculation

Post by 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
Member
Member
Posts: 5452
Joined: Mon Mar 25, 2013 7:01 pm

Re: Tree calculation

Post by 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.
User avatar
iansjack
Member
Member
Posts: 4671
Joined: Sat Mar 31, 2012 3:07 am
Location: Chichester, UK

Re: Tree calculation

Post by 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
Member
Member
Posts: 439
Joined: Fri Feb 11, 2022 4:55 am
Location: behind the keyboard

Re: Tree calculation

Post by 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
Member
Member
Posts: 439
Joined: Fri Feb 11, 2022 4:55 am
Location: behind the keyboard

Re: Tree calculation

Post by 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 ..
User avatar
iansjack
Member
Member
Posts: 4671
Joined: Sat Mar 31, 2012 3:07 am
Location: Chichester, UK

Re: Tree calculation

Post by iansjack »

devc1 wrote: I guess I am a genius ;)
Then you should be able to easily solve this trivial problem. :D

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. :wink:
User avatar
iansjack
Member
Member
Posts: 4671
Joined: Sat Mar 31, 2012 3:07 am
Location: Chichester, UK

Re: Tree calculation

Post by iansjack »

devc1 wrote: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
Member
Member
Posts: 439
Joined: Fri Feb 11, 2022 4:55 am
Location: behind the keyboard

Re: Tree calculation

Post by 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 !
Last edited by devc1 on Sat Aug 12, 2023 4:29 am, edited 1 time in total.
devc1
Member
Member
Posts: 439
Joined: Fri Feb 11, 2022 4:55 am
Location: behind the keyboard

Re: Tree calculation

Post by 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
Posts: 11
Joined: Sat Jan 06, 2024 2:55 am
Libera.chat IRC: @freenode-nf1
Location: India
Contact:

Re: Tree calculation

Post by 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
Post Reply