January 15, 2021
On Friday, 15 January 2021 at 15:18:31 UTC, IGotD- wrote:
> Bump the pointer is a very fast way to allocate memory but what is more interesting is what happens when you return the memory. What does the allocator do with chunks of free memory? Does it put it in a free list, does it merge chunks? I have a feeling that bump the pointer is not the complete algorithm that D uses because of that was the only one, D would waste a lot of memory.

I don't know what DMD does exactly, but I guess this is called an "arena" or something like that? Objective-C does something similar with its autorelease pool.

Basically, you have a point in the call-tree where you know that all work has been done and then you just reclaim everything that is not marked as in-long-term-use. So you don't do the mark phase, you put the burden of marking the object as in use on the object/reference and just sweep. (Or assume that everything can be freed, which fits well with a compiler that is working in discrete stages).

Side note: I incidentally wrote a little allocator cache yesterday that at compile time takes a list of types and then takes the size of those types, sorts it and builds an array of freelists for those specific sizes and caches objects that are freed if they match the desired size (then there is a threshold for the length of the freelist, when that is hit C free() is called. It should be crazy fast too, since I require the free call to provide the type so the correct free list is found at compile time, not at run time.
January 15, 2021
On Friday, 15 January 2021 at 15:20:05 UTC, jmh530 wrote:
> Hypothetically, would it be possible for users to supply their own garbage collector that uses write barriers?

Yes. You could translate Google Chrome's Oilpan to D. It uses library smart pointers for dirty-marking. But it requires you to write a virtual function that points out what should be traced (actually does the tracing for the outgoing pointers from that object):



January 15, 2021
On Friday, 15 January 2021 at 14:35:55 UTC, Ola Fosheim Grøstad wrote:
> On Friday, 15 January 2021 at 14:24:40 UTC, welkam wrote:
>> You can use GC with D compiler by passing -lowmem flag. I didnt measure but I heard it can increase compilation time by 3x.
>
> Thanks for the info. 3x is a lot
Take it with a grain of salt. I heard it long time ago so I might not remember correctly and I didnt measure it myself.

> improved with precise collection
Precise GC is slower than default GC.

> Making it use automatic garbage collection (of some form) would be an interesting benchmark.

-lowmem flag replaces all* allocations with GC allocations so you can benchmark that

On Friday, 15 January 2021 at 14:59:18 UTC, Ola Fosheim Grøstad wrote:
> I think? Or maybe I am missing something?

A write barrier is a peace of code that is inserted before a write to an [object]. Imagine you have a class that has pointer to another class. If you want to change that pointer you need to tell the GC that you changed that pointer so GC can do its magic.
https://en.wikipedia.org/wiki/Write_barrier#In_Garbage_collection

> 3. Make slices and dynamic arrays RC.

Reference counting needs mutation. How do you define immutable RC slice that needs to mutate its reference count? Thats a unsolved problem in D.



January 15, 2021
On Fri, Jan 15, 2021 at 03:18:31PM +0000, IGotD- via Digitalmars-d-learn wrote: [...]
> Bump the pointer is a very fast way to allocate memory but what is more interesting is what happens when you return the memory. What does the allocator do with chunks of free memory? Does it put it in a free list, does it merge chunks? I have a feeling that bump the pointer is not the complete algorithm that D uses because of that was the only one, D would waste a lot of memory.

DMD *never* frees anything.  *That's* part of why it's so fast; it completely drops the complexity of tracking free lists and all of that jazz.

That's also why it's a gigantic memory hog that can be a big embarrassment when run on a low-memory system. :-D

This strategy only works for DMD because a compiler is, by its very nature, a transient process: you read in source files, process them, spit out object files and executables, then you exit.  Add to that the assumption that most PCs these days have gobs of memory to spare, and this allocation scheme completely eliminates memory management overhead. It doesn't matter that memory is never freed, because once the process exits, the OS reclaims everything anyway.

But such an allocation strategy would not work on anything that has to be long-running, or that recycles a lot of memory such that you wouldn't be able to fit it all in memory if you didn't free any of it.


T

-- 
Don't throw out the baby with the bathwater. Use your hands...
January 15, 2021
On Friday, 15 January 2021 at 11:11:14 UTC, Mike Parker wrote:
>
> That's the whole point of being able to mix and match. Anyone avoiding the GC completely is missing it (unless they really, really, must be GC-less).

+1
mix and match is a different style versus only having a GC, or only having lifetimes for everything. And it's quite awesome as a style, since half of things don't need a well-identified owner.
January 15, 2021
On Friday, 15 January 2021 at 15:18:31 UTC, IGotD- wrote:
> I have a feeling that bump the pointer is not the complete algorithm that D uses because of that was the only one, D would waste a lot of memory.

Freeing memory is for loosers :D
https://issues.dlang.org/show_bug.cgi?id=21248

DMD allocates and never frees.
January 15, 2021
On Friday, 15 January 2021 at 15:48:07 UTC, welkam wrote:
> On Friday, 15 January 2021 at 14:35:55 UTC, Ola Fosheim Grøstad wrote:
>> improved with precise collection
> Precise GC is slower than default GC.

D does not have a fully precise GC. The "precise" collector still scans things conservatively when it cannot be certain.

If you combine fully precise collection it with static analysis, then you can reduce the number of paths you follow, but it is a lot of work to implement. So it would take a very motivated individual.

> -lowmem flag replaces all* allocations with GC allocations so you can benchmark that

Interesting idea. There are compilers that use GC written in other languages. It is a nice baseline test, especially since there are not many large commonly known programs for D to do realistic benchmarks with.

> A write barrier is a peace of code that is inserted before a write to an [object].

Not a write to the object, but a modified pointer. The write barrier is invoked when you switch a pointer from one object to another one. Then you mark the object, so you need 2 free bits in each object to use for marking.

But my uncertainty was related to how to optimize away barrier that has no impact on the final collection. It is easy to make mistakes when doing such optimizations. The goal should be to invoke as few barriers as possible by static analysis.

> Reference counting needs mutation. How do you define immutable RC slice that needs to mutate its reference count? Thats a unsolved problem in D.

D needs more fine grained immutable, for sure.

January 15, 2021
On Friday, 15 January 2021 at 15:50:59 UTC, Guillaume Piolat wrote:
> On Friday, 15 January 2021 at 11:11:14 UTC, Mike Parker wrote:
>>
>> That's the whole point of being able to mix and match. Anyone avoiding the GC completely is missing it (unless they really, really, must be GC-less).
>
> +1
> mix and match is a different style versus only having a GC, or only having lifetimes for everything. And it's quite awesome as a style, since half of things don't need a well-identified owner.


What do you mean by "mix and match"? If it means shutting down the GC after initialization then it can easily backfire for more complicated software that accidentally calls code that relies on the GC.

Until someone can describe a strategy that works for a full application, e.g. an animation-editor or something like that, it is really difficult to understand what is meant by it.


January 15, 2021
On Friday, 15 January 2021 at 15:36:37 UTC, Ola Fosheim Grøstad wrote:
> On Friday, 15 January 2021 at 15:20:05 UTC, jmh530 wrote:
>> Hypothetically, would it be possible for users to supply their own garbage collector that uses write barriers?
>
> Yes. You could translate Google Chrome's Oilpan to D. It uses library smart pointers for dirty-marking. But it requires you to write a virtual function that points out what should be traced (actually does the tracing for the outgoing pointers from that object):

The library smart pointers would make it difficult to interact with existing D GC code though.
January 15, 2021
On Friday, 15 January 2021 at 15:50:50 UTC, H. S. Teoh wrote:
>
> DMD *never* frees anything.  *That's* part of why it's so fast; it completely drops the complexity of tracking free lists and all of that jazz.
>
> That's also why it's a gigantic memory hog that can be a big embarrassment when run on a low-memory system. :-D
>
> This strategy only works for DMD because a compiler is, by its very nature, a transient process: you read in source files, process them, spit out object files and executables, then you exit.  Add to that the assumption that most PCs these days have gobs of memory to spare, and this allocation scheme completely eliminates memory management overhead. It doesn't matter that memory is never freed, because once the process exits, the OS reclaims everything anyway.
>
> But such an allocation strategy would not work on anything that has to be long-running, or that recycles a lot of memory such that you wouldn't be able to fit it all in memory if you didn't free any of it.
>
>
> T

Are we talking about the same things here? You mentioned DMD but I was talking about programs compiled with DMD (or GDC, LDC), not the nature of the DMD compiler in particular.

Bump the pointer and never return any memory might acceptable for short lived programs but totally unacceptable for long running programs, like a browser you are using right now.

Just to clarify, in a program that is made in D with the default options, will there be absolutely no memory reclamation?