View mode: basic / threaded / horizontal-split · Log in · Help
June 08, 2006
Re: GC, the simple solution
Jeff Parsons wrote:
> 
> What I'm really curious about, however, is how important this is to 
> _other_ people - especially Walter. Would it be reasonable to say that 
> it seems D has been designed largely without long-term real-time 
> performance in mind? Sure, there are workarounds, but I haven't seen 
> anything elegant yet that will let me use D for such applications 
> without making my memory management more complicated than it would have 
> been in C++. Is anything in the works?

The spec doesn't contain any language forbidding such an approach, but I 
don't think the popular compilers will support it by default.  Certainly 
not any time soon, at any rate.  The "problem" with incremental GC is 
that it requires extra code generation for all pointer modifications to 
signal the garbage collector that some re-scanning may be necessary. 
This has obvious performance implications for small apps that don't ever 
actually need to collect, but tends to level out as run time increases. 
  And, of course, the potential for progress guarantees (possible with 
incremental GC, but not at all common) is a huge bonus for realtime 
programming.  That aside, there may be other approaches to garbage 
collection that would make everyone happy and that don't require 
additional code generation.  If you know of one, please say so.  My own 
knowledge of the topic is limited to what I've read in research papers.


Sean
June 09, 2006
Re: GC, the simple solution
On 06/08/2006 06:04 PM, Sean Kelly wrote:
> Jeff Parsons wrote:
> 
[snip]
>> performance in mind? Sure, there are workarounds, but I haven't seen 
>> anything elegant yet that will let me use D for such applications 
>> without making my memory management more complicated than it would 
>> have been in C++. Is anything in the works?
> 
> 
> The spec doesn't contain any language forbidding such an approach, but I 
> don't think the popular compilers will support it by default.  Certainly 
[snip]
> programming.  That aside, there may be other approaches to garbage 
> collection that would make everyone happy and that don't require 
> additional code generation.  If you know of one, please say so.  My own 
> knowledge of the topic is limited to what I've read in research papers.
You could define a policy pointer which could have as one policy, the
current Boehm collector.  IOW, any ptr<BW> p(T) on the stack would be a
root pointer and each data structure would have a map of ptr<BW>
locations.  Similarly, there could be ptr<Copy> or ptr<IncBw> or even
ptr<deterministic> and ptr<collected> instead of the

  class [collected] SomeClass{...};
  class [deterministic] OtherClass{...}

proposed by Adrei here:

  http://tinyurl.com/o5zpm

This, of course, would require cooperation from the compiler, but
the same it would be true of:

  class [collected] SomeClass{...};

it's just that some specializations, ptr<collected>, would be
predetermined and others, for example, user-defined ones,
would not.
June 09, 2006
Re: GC, the simple solution
Jeff Parsons wrote:
> My _only_ significant beef with D so far as been the unbound time for a 
> garbage collection; therefore, if an incremental garbage collector built 
> into D could guarantee me a set maximum time would be taken for each 
> garbage collection (which I would manually induce as often as possible) 
> then unless the efficiency hit is TERRIBLE I would be all over it.

If you're looking for a *guarantee*, then you cannot even use malloc(). 
Malloc has unbounded time, and is not predictable.

The approach most real time programmers use to deal with this is to 
preallocate all needed data before entering the real time section, and 
the real time section does no malloc's or free's.

Also, you can use malloc and free in D, in exactly the same way you 
would in C.
June 09, 2006
Re: GC, the simple solution
Walter Bright wrote:
> Jeff Parsons wrote:
>> My _only_ significant beef with D so far as been the unbound time for 
>> a garbage collection; therefore, if an incremental garbage collector 
>> built into D could guarantee me a set maximum time would be taken for 
>> each garbage collection (which I would manually induce as often as 
>> possible) then unless the efficiency hit is TERRIBLE I would be all 
>> over it.
> 
> If you're looking for a *guarantee*, then you cannot even use malloc(). 
> Malloc has unbounded time, and is not predictable.

For what it's worth, I have read papers describing hard real-time 
incremental garbage collectors, but I haven't yet seen one available 
outside research circles.  I'd like to give one a shot at some point, 
but I've far too many other distractions to know when that will be.

If anyone is interested however, some of the papers are available here:

http://www.cs.utexas.edu/users/oops/papers.html

See papers 11 and 14.

> The approach most real time programmers use to deal with this is to 
> preallocate all needed data before entering the real time section, and 
> the real time section does no malloc's or free's.

This is certainly the easiest and probably the safest method.


Sean
June 09, 2006
Re: GC, the simple solution
On Thu, 08 Jun 2006 22:18:24 -0700, Walter Bright wrote:


> The approach most real time programmers use to deal with this is to 
> preallocate all needed data before entering the real time section, and 
> the real time section does no malloc's or free's.
> 
> Also, you can use malloc and free in D, in exactly the same way you 
> would in C.

It seems obvious that if one doesn't want the Garbage Collector to collect
garbage, one doesn't create any garbage for it to collect. ;-)

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocrity!"
9/06/2006 4:44:56 PM
June 09, 2006
Re: GC, the simple solution
Derek Parnell wrote:
> On Thu, 08 Jun 2006 22:18:24 -0700, Walter Bright wrote:
> 
> 
>> The approach most real time programmers use to deal with this is to 
>> preallocate all needed data before entering the real time section, and 
>> the real time section does no malloc's or free's.
>>
>> Also, you can use malloc and free in D, in exactly the same way you 
>> would in C.
> 
> It seems obvious that if one doesn't want the Garbage Collector to collect
> garbage, one doesn't create any garbage for it to collect. ;-)

This gets sticky if one wants to use strings in D though, as there's no 
real way to make them work outside of the garbage collector mechanism. 
Sure we could use C-style pointers, but it's not a terribly attractive 
option.  I suppose the alternative would be a class with a custom 
allocator method.


Sean
June 09, 2006
Re: GC, the simple solution
Sean Kelly wrote:
> Walter Bright wrote:
>> The approach most real time programmers use to deal with this is to 
>> preallocate all needed data before entering the real time section, and 
>> the real time section does no malloc's or free's.
> 
> This is certainly the easiest and probably the safest method.

Yup. It gets the job done.

Real time threads should be considered a very valuable resource, and as 
such all possible computation should be removed from them and put into 
non-realtime threads.
June 09, 2006
Re: GC, the simple solution
Sean Kelly wrote:
> Derek Parnell wrote:
>> On Thu, 08 Jun 2006 22:18:24 -0700, Walter Bright wrote:
>>
>>
>>> The approach most real time programmers use to deal with this is to 
>>> preallocate all needed data before entering the real time section, 
>>> and the real time section does no malloc's or free's.
>>>
>>> Also, you can use malloc and free in D, in exactly the same way you 
>>> would in C.
>>
>> It seems obvious that if one doesn't want the Garbage Collector to 
>> collect
>> garbage, one doesn't create any garbage for it to collect. ;-)
> 
> This gets sticky if one wants to use strings in D though, as there's no 
> real way to make them work outside of the garbage collector mechanism.
> Sure we could use C-style pointers, but it's not a terribly attractive 
> option.

You can use D arrays. Just allocate them using malloc (or statically 
allocate them). Don't concatenate them.

Though I would ask why the real time code was allocating strings?

C is very good for writing real time code, and you can write "C"-style 
code in D, and it will behave exactly like the corresponding C code. You 
can call printf, strcpy, malloc, etc., which will behave just like C's 
printf, strcpy, and malloc because they *are* C's functions. It will not 
do a gc collect unless the code allocates gc memory, and it will ONLY do 
a gc collect during such an allocation.

Heck, my old Empire game was written in C. I renamed the files from .c 
to .d, did a few minor syntactic edits, and voila! it was now in D. It 
runs exactly the same.

But the bottom line is that a real time thread should not be doing 
storage allocation. It shouldn't be calling new, or malloc. It shouldn't 
do storage allocation regardless of whether it is written in D, C, C++, 
or assembler.
June 09, 2006
Re: GC, the simple solution
Walter Bright wrote:
> Sean Kelly wrote:
>> Derek Parnell wrote:
>>> On Thu, 08 Jun 2006 22:18:24 -0700, Walter Bright wrote:
>>>
>>>
>>>> The approach most real time programmers use to deal with this is to 
>>>> preallocate all needed data before entering the real time section, 
>>>> and the real time section does no malloc's or free's.
>>>>
>>>> Also, you can use malloc and free in D, in exactly the same way you 
>>>> would in C.
>>>
>>> It seems obvious that if one doesn't want the Garbage Collector to 
>>> collect
>>> garbage, one doesn't create any garbage for it to collect. ;-)
>>
>> This gets sticky if one wants to use strings in D though, as there's 
>> no real way to make them work outside of the garbage collector mechanism.
>> Sure we could use C-style pointers, but it's not a terribly attractive 
>> option.
> 
> You can use D arrays. Just allocate them using malloc (or statically 
> allocate them). Don't concatenate them.

So then I'd just manually set the ptr and len members?  Sounds 
reasonable, provided everyone behaves and uses the copy on write idiom 
you suggest.

> Though I would ask why the real time code was allocating strings?

I was mostly thinking about this in the context of just how much 
allocation pretty much must be performed by the GC for applications with 
special memory requirements (gigabytes of data, for example).  It just 
seemed to have an overlap insofar as this sort of programming is concerned.

> C is very good for writing real time code, and you can write "C"-style 
> code in D, and it will behave exactly like the corresponding C code. You 
> can call printf, strcpy, malloc, etc., which will behave just like C's 
> printf, strcpy, and malloc because they *are* C's functions. It will not 
> do a gc collect unless the code allocates gc memory, and it will ONLY do 
> a gc collect during such an allocation.

At times I've considered extending thread support to allow for the 
creation of detached threads, but it simply seems to error-prone to be 
worthwhile.  I think you're right in that if someone is doing real-time 
programming then they shouldn't expect much hand-holding, because the 
assumptions involved offer too great a risk of unexpected behavior.

> Heck, my old Empire game was written in C. I renamed the files from .c 
> to .d, did a few minor syntactic edits, and voila! it was now in D. It 
> runs exactly the same.

Yup.  Though it's worth noting that D has been heavily influenced by 
your particular programming style.  Not at all a bad thing, but it does 
imply that you are less likely than anyone else to experience code 
translation problems :-)  On a related note, I sometimes wonder if Sid 
Meier credits you anywhere for effectively creating the genre that's 
made him so successful ;-)

> But the bottom line is that a real time thread should not be doing 
> storage allocation. It shouldn't be calling new, or malloc. It shouldn't 
> do storage allocation regardless of whether it is written in D, C, C++, 
> or assembler.

True enough.


Sean
Sean
June 09, 2006
Re: GC, the simple solution
Sean Kelly wrote:
> Walter Bright wrote:
>> You can use D arrays. Just allocate them using malloc (or statically 
>> allocate them). Don't concatenate them.
> So then I'd just manually set the ptr and len members?  Sounds 
> reasonable, provided everyone behaves and uses the copy on write idiom 
> you suggest.

int *p = cast(int *)calloc(dim, sizeof(int));
int[] a = p[0 .. dim];

>> C is very good for writing real time code, and you can write "C"-style 
>> code in D, and it will behave exactly like the corresponding C code. 
>> You can call printf, strcpy, malloc, etc., which will behave just like 
>> C's printf, strcpy, and malloc because they *are* C's functions. It 
>> will not do a gc collect unless the code allocates gc memory, and it 
>> will ONLY do a gc collect during such an allocation.
> At times I've considered extending thread support to allow for the 
> creation of detached threads, but it simply seems to error-prone to be 
> worthwhile.  I think you're right in that if someone is doing real-time 
> programming then they shouldn't expect much hand-holding, because the 
> assumptions involved offer too great a risk of unexpected behavior.

I agree that realtime programming is a special type of programming, and 
that someone doing it should be a more advanced programmer. You can't 
just take any random code (in any language), make it realtime, and 
expect it to work properly. It's got to be engineered for the 
peculiarities of realtime requirements.


>> Heck, my old Empire game was written in C. I renamed the files from .c 
>> to .d, did a few minor syntactic edits, and voila! it was now in D. It 
>> runs exactly the same.
> 
> Yup.  Though it's worth noting that D has been heavily influenced by 
> your particular programming style.  Not at all a bad thing, but it does 
> imply that you are less likely than anyone else to experience code 
> translation problems :-)  On a related note, I sometimes wonder if Sid 
> Meier credits you anywhere for effectively creating the genre that's 
> made him so successful ;-)

Nope :-)
1 2 3 4 5 6 7
Top | Discussion index | About this forum | D home