Recent

Author Topic: IRC channel  (Read 6442 times)

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 8618
  • Debugger - SynEdit - and more
    • wiki
Re: IRC channel
« Reply #90 on: December 09, 2022, 04:14:15 am »
Memory fragmentation in today's O/Ss results in memory being wasted.

Only in today's OS? I though it was a timeless phenomenon, that having memory in a state in which it can't be used meant it was wasted....

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 8618
  • Debugger - SynEdit - and more
    • wiki
Re: IRC channel
« Reply #91 on: December 09, 2022, 04:42:32 am »
Can you give me an example where you was in need to "defragment" memory? Just to be sure, we are now talking about RAM in this IRC channel thread, right?

The question wasn't directed at me, but heck I'll add some response to it anyway.

Say you are writing a firewall (for a server on the net). And you are required to deliver for 6 or 7 nines availability. That means your app must run continuously for the entire year, ideally for many years without ever being restarted.
You may also be bound to limited hardware. Most firewalls (if they have there own hardware) probably don't come with 100GB of RAM. So you don't even want to have "just 10%" of the RAM stuck in fragmentation.

One benefit of pre-allocating - if you recall my nginx - example: The software knows it has 1000 objects. It has a counter what is used, if it has 0 left, you know exactly when and where the error needs to be handled. There is no "AllocMem" somewhere deeply nested in a subroutine. No need to return that "out of mem" error all the way up to the top level caller.
(Though the benefit on the error handling is a side effect, and you can reach that independent of dealing with fragmentation)

I grant you, that is a pretty special case (and likely a lot of firewalls have some dynamic alloc going on).

And well, I would think that there are lots of programmers (including experienced ones) who don't really know about mem fragmentation (and no, I don't mean JavarScript users / Programmers in a language that has "AllocMem" and "FreeMem").
And of those who know, very few have ever really a reason to think about it.





440bx

  • Hero Member
  • *****
  • Posts: 3265
Re: IRC channel
« Reply #92 on: December 09, 2022, 05:18:46 am »
Memory fragmentation in today's O/Ss results in memory being wasted.

Only in today's OS? I though it was a timeless phenomenon, that having memory in a state in which it can't be used meant it was wasted....
Yes, you are absolutely right.  What I meant to emphasize is that in today's O/Ss fragmentation only results in memory being wasted. In previous O/Ss, particularly 16 bit O/Ss, fragmentation could very well result in the program no longer being able to allocate memory.  Getting to that point with a 32 bit or 64 bit O/S is a lot harder and unlikely (particularly in a 64 bit O/S.)
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 SP1 64bit.

KodeZwerg

  • Hero Member
  • *****
  • Posts: 904
  • Fifty shades of code.
    • Delphi & FreePascal
Re: IRC channel
« Reply #93 on: December 09, 2022, 11:54:54 am »
I appreciate your answers! @440bx @bogen85 @martin_fr  O:-)
« Last Edit: Tomorrow at 31:76:97 by KodeZwerg »

alpine

  • Hero Member
  • *****
  • Posts: 630
Re: IRC channel
« Reply #94 on: December 09, 2022, 01:52:05 pm »
I’m not sure how to create pools from inside pascal code or is it set somewhere else?
TTBOMK, there is no mechanism in Pascal, including FPC, to create separate/independent pools of memory.  In Windows those can be created using HeapCreate, HeapDestroy, VirtualAlloc(Ex), VirtualFree for Heaps and Virtual memory respectively.  I know that Linux offers similar functions for Virtual memory management but, I don't know if it offers creation and destruction of heaps.
Actually, there is a way in FPC (also in Delphi) to write your own heap manager. That is the way the fastmm, heaptrc and cmem units were written.
The current FPC heap manager do implement pools at least for a small memory blocks. So and cmem (through msvcrt/clib).
I realized that only when I wrote my own (application specific) MM with extensible pooling and found that it's not giving me the performance benefit I've expected compared to the standard and cmem ones.

If the memory does get too fragmented it seems like it could be de fragmented similar to how a disk is defragmented?
Yes, it is similar but, not quite the same.  The difference is mostly based on the fact that on a disk there is an atomic allocation size (usually the cluster, which in Windows is usually 4K), a file can be made of a linked list of clusters.  The file is considered fragmented when the clusters aren't contiguous. 

In memory, particularly heaps, the problem is different.  Free heap blocks, unlike a disk cluster, can vary greatly in size which causes problems when attempting to reuse them: either they may be too small, therefore unusable, or too large which, if used for a smaller structure, means some of the memory is simply wasted.
With a recent CPU's incorporating VM support hardware and capable of address linearization, the task should be not very different than disk/cluster de-fragmentation. To what extent this is implemented in the operating system and whether this simply pushes the problem to another level is a separate matter. There are known allocation patterns which makes Windows to extend the process commit size beyond the limits.
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

440bx

  • Hero Member
  • *****
  • Posts: 3265
Re: IRC channel
« Reply #95 on: December 09, 2022, 04:02:10 pm »
Actually, there is a way in FPC (also in Delphi) to write your own heap manager.
writing your own heap manager is a very different thing than being able to create multiple heaps which is what I was referring to.  As I stated previously, TTBOMK, FPC does not offer that capability.

With a recent CPU's incorporating VM support hardware and capable of address linearization, the task should be not very different than disk/cluster de-fragmentation.
VM support or otherwise, it is very different.  When the heap receives a request for "n" kilobytes, say for the sake of argument 12kb, a heap _must_ provide a _contiguous_ 12kb whereas a request for the same amount of storage on disk can be filled with 3 clusters of 4kb each.  A heap does _not_ have that luxury.
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 SP1 64bit.

PascalDragon

  • Hero Member
  • *****
  • Posts: 4872
  • Compiler Developer
Re: IRC channel
« Reply #96 on: December 09, 2022, 04:56:28 pm »
If the memory does get too fragmented it seems like it could be de fragmented similar to how a disk is defragmented?
Yes, it is similar but, not quite the same.  The difference is mostly based on the fact that on a disk there is an atomic allocation size (usually the cluster, which in Windows is usually 4K), a file can be made of a linked list of clusters.  The file is considered fragmented when the clusters aren't contiguous. 

In memory, particularly heaps, the problem is different.  Free heap blocks, unlike a disk cluster, can vary greatly in size which causes problems when attempting to reuse them: either they may be too small, therefore unusable, or too large which, if used for a smaller structure, means some of the memory is simply wasted.
With a recent CPU's incorporating VM support hardware and capable of address linearization, the task should be not very different than disk/cluster de-fragmentation. To what extent this is implemented in the operating system and whether this simply pushes the problem to another level is a separate matter. There are known allocation patterns which makes Windows to extend the process commit size beyond the limits.

You can't defragment the virtual address space as that would need to change the pointers that are stored e.g. in the stack or where ever. You can defragment your own heap only with deallocated areas by combining them again or whatever depending on your heap management algorithm.

alpine

  • Hero Member
  • *****
  • Posts: 630
Re: IRC channel
« Reply #97 on: December 10, 2022, 01:03:47 pm »
You can't defragment the virtual address space as that would need to change the pointers that are stored e.g. in the stack or where ever. You can defragment your own heap only with deallocated areas by combining them again or whatever depending on your heap management algorithm.
My point was that, theoretically by using MMU, the fragmentation could be avoided by redirecting/merging physical RAM pages in the address translation table (which could be seen as additional redirection, like handles in GlobalLock). But since the MMU is managed exclusively by the operating system, this is almost impractical unless one is working with the bare metal.
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

Joanna

  • Full Member
  • ***
  • Posts: 227
Re: IRC channel
« Reply #98 on: December 11, 2022, 12:44:19 pm »
The idea of using handles that point to pointers to memory locations seems  like a good idea. It seems like being able to defragment memory is very important for programs expected to run for a long time without stopping.

The logic of defrafmenting memory seems like it would be fairly simple kind of like defragmenting people in a theatre by making them all scoot over and remove gaps
Come chat on IRC .. https://libera.chat/guides/
IRC.LIBERA.CHAT  Ports [6667 plaintext ] or [6697 secure] channels  #fpc #lazarus #pascal 
type /msg nickserv help register to get started

440bx

  • Hero Member
  • *****
  • Posts: 3265
Re: IRC channel
« Reply #99 on: December 11, 2022, 01:23:06 pm »
The idea of using handles that point to pointers to memory locations seems  like a good idea.
It's one of those ideas that seems good at the beginning but, time reveals it's not such a "good idea" in the long run.  The problem is, the program cannot access any memory block without first locking the handle which is what returns a pointer to the memory block.  Locking the handle has the effect of telling the O/S that, that memory block cannot be moved.    Without the program's cooperation, the O/S will usually not be able to achieve a reasonably decent level of defragmentation.  With program cooperation, the O/S should be able to defragment the memory BUT, the problem then becomes the amount of time the defragmentation may take and, timing it in such a way that it doesn't significantly affect its smooth operation.

It seems like being able to defragment memory is very important for programs expected to run for a long time without stopping.
What's really important is to _avoid_ fragmentation to an extent where it becomes a problem.  Once it has become a problem, there is no solution that is free of potentially very undesirable consequences.

The logic of defrafmenting memory seems like it would be fairly simple kind of like defragmenting people in a theatre by making them all scoot over and remove gaps
It's very different than having people scoot over to remove gaps because, in the case of people in a theater there isn't "anyone" keeping track  and _depending_ on where each person is seated (i.e, having a pointer to the person that needs to be updated if and when the person moves.)

It's usually quite easy to _avoid_ fragmentation, it only requires a little bit of upfront thinking about the program's design.
FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 SP1 64bit.

Bogen85

  • Sr. Member
  • ****
  • Posts: 376
Re: IRC channel
« Reply #100 on: December 11, 2022, 01:26:59 pm »
The idea of using handles that point to pointers to memory locations seems  like a good idea. It seems like being able to defragment memory is very important for programs expected to run for a long time without stopping.

The logic of defrafmenting memory seems like it would be fairly simple kind of like defragmenting people in a theatre by making them all scoot over and remove gaps

But at a higher level, how does this translate into use by by the data structures and current live stack frames that are using the pointers?

You move memory blocks around in a processor level multi-threaded application everything using those blocks is going to crash.

The handles would then have to essentially be indirect pointers (so regular code is not getting actual pointers any more). Even with them being indirect, there would need to be synchronization to make sure sure nothing is using a live pointer. So something like a stop the world garbage collection sweep. Then on top of that, the handles are now essentially data structures, and what is going to defragment them?

You can't defragment the virtual address space as that would need to change the pointers that are stored e.g. in the stack or where ever. You can defragment your own heap only with deallocated areas by combining them again or whatever depending on your heap management algorithm.
My point was that, theoretically by using MMU, the fragmentation could be avoided by redirecting/merging physical RAM pages in the address translation table (which could be seen as additional redirection, like handles in GlobalLock). But since the MMU is managed exclusively by the operating system, this is almost impractical unless one is working with the bare metal.

If we talking about de-fragmenting at an MMU level, on processor level multi-threading that is still likely going to be stop the world for the process using the region be de-fragmented.


Then there is page size thrown into the mix, and OS level memory allocation and freeing being both expensive time wise (on OSes where crossing the syscall boundry is expensive).
This bug report highlights the page size issue.
https://bugzilla.redhat.com/show_bug.cgi?id=2001569
Quote
Description of problem: At the moment the aarch64 kernel builds of RHEL8 assume a 64kB pagesize, which works fine most of the time. However when trying to run in a  virtualized environment on Apple M1 devices via Parallels Desktop it is not possible to boot RHEL8 because the M1 chips only support 4kB & 16kB pagesizes. Ubuntu and Debian are compatible with Parallels on these devices, so it should be possible for RHEL as well.

On Linux at least (and would likely apply to other *nix like the common BSDs) Because allocation at syscall level is both expensive and not fine grained (you can't just allocate 32 bytes for a string data structure, you need to allocate at least the page size, be that 4K, 16K, or 64K as being discussed in the above bug report) then most language runtime do there own heap management, so the individual pointers to data structures are not mapped at the logical address to physical address MMU translation layer.

As such, the run-times do their own pool management, and often allocation much larger memory pools than what was requested, and don't give those pools back to operating system right away (which is expensive) when data is freed, as they make the memory blocks within those pools available to other parts or your program.

Most of the memory fragmentation being discussed here I'm assuming is taking place at the language runtime level. And de-fragmenting at that level is using logical addresses, not physical addresses.
And just using "handles" everywhere is not a simple solution to the problem, as I discussed at the beginning of this reply.



« Last Edit: December 11, 2022, 01:29:54 pm by Bogen85 »

Bogen85

  • Sr. Member
  • ****
  • Posts: 376
Re: IRC channel
« Reply #101 on: December 11, 2022, 01:28:26 pm »
The idea of using handles that point to pointers to memory locations seems  like a good idea.
It's one of those ideas that seems good at the beginning but, time reveals it's not such a "good idea" in the long run.  The problem is, the program cannot access any memory block without first locking the handle which is what returns a pointer to the memory block.  Locking the handle has the effect of telling the O/S that, that memory block cannot be moved.    Without the program's cooperation, the O/S will usually not be able to achieve a reasonably decent level of defragmentation.  With program cooperation, the O/S should be able to defragment the memory BUT, the problem then becomes the amount of time the defragmentation may take and, timing it in such a way that it doesn't significantly affect its smooth operation.

It seems like being able to defragment memory is very important for programs expected to run for a long time without stopping.
What's really important is to _avoid_ fragmentation to an extent where it becomes a problem.  Once it has become a problem, there is no solution that is free of potentially very undesirable consequences.

The logic of defrafmenting memory seems like it would be fairly simple kind of like defragmenting people in a theatre by making them all scoot over and remove gaps
It's very different than having people scoot over to remove gaps because, in the case of people in a theater there isn't "anyone" keeping track  and _depending_ on where each person is seated (i.e, having a pointer to the person that needs to be updated if and when the person moves.)

It's usually quite easy to _avoid_ fragmentation, it only requires a little bit of upfront thinking about the program's design.

You beat me to it and answered more succinctly, thanks!


alpine

  • Hero Member
  • *****
  • Posts: 630
Re: IRC channel
« Reply #102 on: December 11, 2022, 01:36:04 pm »
The idea of using handles that point to pointers to memory locations seems  like a good idea. It seems like being able to defragment memory is very important for programs expected to run for a long time without stopping.
It is indeed important.

Bit IMO it is much simpler to pre-allocate memory chunks, put them in a list (aka "pool") and then take it from there when needed and put them back into the pool for latter reuse.

The logic of defrafmenting memory seems like it would be fairly simple kind of like defragmenting people in a theatre by making them all scoot over and remove gaps
Yes, but such a 'house keeping' is a time consuming and introduces unpredictability with regard to the response time, etc. It is better simply to avoid fragmentation instead of dealing with it.

Edit:

@Bogen85
You're pretty fast, I'll need a bit to reaching you.

I think we got too far with that MMU thing, it is clear that the managers are that way for a reason. May be we should point to a more practical patterns for the Joanna questions, e.g. pools, not using dynarrays, etc.

Anyway, putting walls of text is not quite IRC'ish :)
« Last Edit: December 11, 2022, 01:50:53 pm by y.ivanov »
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

Bogen85

  • Sr. Member
  • ****
  • Posts: 376
Re: IRC channel
« Reply #103 on: December 11, 2022, 01:39:31 pm »
The idea of using handles that point to pointers to memory locations seems  like a good idea. It seems like being able to defragment memory is very important for programs expected to run for a long time without stopping.

The logic of defrafmenting memory seems like it would be fairly simple kind of like defragmenting people in a theatre by making them all scoot over and remove gaps

But at a higher level, how does this translate into use by by the data structures and current live stack frames that are using the pointers?

You move memory blocks around in a processor level multi-threaded application everything using those blocks is going to crash.

The handles would then have to essentially be indirect pointers (so regular code is not getting actual pointers any more). Even with them being indirect, there would need to be synchronization to make sure sure nothing is using a live pointer. So something like a stop the world garbage collection sweep. Then on top of that, the handles are now essentially data structures, and what is going to defragment them?
...

On the stack frame issue, that might make this kind of de-fragmentation impossible. (maybe not impossible in theory, but in practice).

Is your de-fragmenteger going to stop the world, unwind every stack frame looking for where the actual memory addresses were extracted and used, and patch the addresses in the frame?

Many processors don't have the support for indirect memory for pointers, so indirect always access could not be enforced.

Also:

Is it going to analyze and patch all CPU level caches for the threads involved to do the same?
Is it going to inspect any swapped out to disk (or to compressed ram disks, aka ZRAM) memory for processes do the same?

All the above makes it horribly complex and very prone to error if not done perfectly.
« Last Edit: December 11, 2022, 01:42:18 pm by Bogen85 »

PascalDragon

  • Hero Member
  • *****
  • Posts: 4872
  • Compiler Developer
Re: IRC channel
« Reply #104 on: December 11, 2022, 09:40:58 pm »
You can't defragment the virtual address space as that would need to change the pointers that are stored e.g. in the stack or where ever. You can defragment your own heap only with deallocated areas by combining them again or whatever depending on your heap management algorithm.
My point was that, theoretically by using MMU, the fragmentation could be avoided by redirecting/merging physical RAM pages in the address translation table (which could be seen as additional redirection, like handles in GlobalLock). But since the MMU is managed exclusively by the operating system, this is almost impractical unless one is working with the bare metal.

Again: that doesn't solve the fragmentation of the virtual address space, which is what your application sees. It already doesn't matter where the physical pages are located, the OS will simply pick the next best free physical memory page for the allocation of a virtual page.

 

TinyPortal © 2005-2018