www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.experimental.allocator.make should throw on out-of-memory

reply Alex Parrill <initrd.gz gmail.com> writes:
I'm proposing that std.experimental.allocator.make, as well as 
its friends, throw an exception when the allocator cannot satisfy 
a request instead of returning null.

These are my reasons for doing so:

* It eliminates the incredibly tedious, annoying, and 
easy-to-forget boilerplate after every allocation to check if the 
allocation succeeded.

* Being unable to fulfill an allocation is an exceptional case 
[1], thus exceptions are a good tool for handling it. Performance 
on the out-of-memory case isn't a big issue; 99% of programs, 
when out of memory, either exit immediately or display an "out of 
memory" message to the user and cancel the operation.

* It fails faster and safer. It's better to error out immediately 
with a descriptive "out of memory" message instead of potentially 
continuing with an invalid pointer and potentially causing an 
invalid memory access, or worse, a vulnerability, if the 
developer forgot to check (which is common for boilerplate code).

* Creating a standard out-of-memory exception will make it easier 
to catch, instead of catching each library's own custom exception 
that they will inevitably define.

Hopefully, since std.experimental.allocator is experimental, 
we'll be allowed to make such backwards-incompatible changes.

What are other peoples thoughts on this? Or has this brought up 
before and I missed the discussion?

[1] It may not be very exceptional for "building-block" 
allocators that start with small but fast allocators that may 
fail a lot, in which case returning null is appropriate. However, 
AFAIK allocators internally use the `allocate` method of the 
allocator, not make, et al., so they should be unaffected by this 
change.
Apr 19 2016
next sibling parent reply Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
On Tuesday, 19 April 2016 at 22:28:27 UTC, Alex Parrill wrote:

 * It eliminates the incredibly tedious, annoying, and 
 easy-to-forget boilerplate after every allocation to check if 
 the allocation succeeded.


FWIW, you can turn a false-ish (!value) function call result into 
an exception by sticking .enforce() at the end. Perhaps this is 
the use case for a Maybe type.
Apr 19 2016
parent reply Alex Parrill <initrd.gz gmail.com> writes:
On Wednesday, 20 April 2016 at 01:59:31 UTC, Vladimir Panteleev 
wrote:

 On Tuesday, 19 April 2016 at 22:28:27 UTC, Alex Parrill wrote:

 * It eliminates the incredibly tedious, annoying, and 
 easy-to-forget boilerplate after every allocation to check if 
 the allocation succeeded.


 FWIW, you can turn a false-ish (!value) function call result 
 into an exception by sticking .enforce() at the end. Perhaps 
 this is the use case for a Maybe type.


Yes, enforce helps (and I forgot it reruns its argument), but its 
still boilerplate, and it throws a generic "enforcement failed" 
exception instead of a more specific "out of memory" exception 
unless you remember to specify your own exception or message.
Apr 20 2016
parent Alex Parrill <initrd.gz gmail.com> writes:
On Wednesday, 20 April 2016 at 18:07:05 UTC, Alex Parrill wrote:

 Yes, enforce helps (and I forgot it reruns its argument), but 
 its still boilerplate, and it throws a generic "enforcement 
 failed" exception instead of a more specific "out of memory" 
 exception unless you remember to specify your own exception or 
 message.


s/rerun/return/
Apr 20 2016
prev sibling next sibling parent reply Minas Mina <minas_0 hotmail.co.uk> writes:
On Tuesday, 19 April 2016 at 22:28:27 UTC, Alex Parrill wrote:

 I'm proposing that std.experimental.allocator.make, as well as 
 its friends, throw an exception when the allocator cannot 
 satisfy a request instead of returning null.

 [...]


I believe it was designed this way so that it can be used in 
 nogc code, although I might be wrong.
Apr 20 2016
next sibling parent reply Basile Burg <b2.temp gmx.com> writes:
On Wednesday, 20 April 2016 at 19:18:58 UTC, Minas Mina wrote:

 On Tuesday, 19 April 2016 at 22:28:27 UTC, Alex Parrill wrote:

 I'm proposing that std.experimental.allocator.make, as well as 
 its friends, throw an exception when the allocator cannot 
 satisfy a request instead of returning null.

 [...]


 I believe it was designed this way so that it can be used in 
  nogc code, although I might be wrong.


I don't know but in the worst case a system exist to throw  nogc 
exceptions that would work in this case (the message doesn't have 
to be customized so it can be static):

 nogc  safe
void throwStaticEx(T, string file = __FILE__, size_t line = 
__LINE__)()
{
     static const e = new T(file, line);
     throw e;
}

but personaly I 'd prefer that the allocators remains as they are.
Apr 20 2016
parent Nick Treleaven <ntrel-pub mybtinternet.com> writes:
On Wednesday, 20 April 2016 at 19:32:01 UTC, Basile Burg wrote:

 a system exist to throw  nogc exceptions that would work in 
 this case (the message doesn't have to be customized so it can 
 be static):

  nogc  safe
 void throwStaticEx(T, string file = __FILE__, size_t line = 
 __LINE__)()
 {
     static const e = new T(file, line);
     throw e;
 }


Nice idea, I tweaked it a bit to accept custom arguments to T 
e.g. a message:
http://dpaste.dzfl.pl/5e58c0142ccd

throw staticEx!(Exception, "Look ma,  nogc exception!");

That works, but I couldn't get the staticEx(string msg) overload 
to compile. Anyway, maybe something like this could go in 
std.exception?
Apr 21 2016
prev sibling parent Alex Parrill <initrd.gz gmail.com> writes:
On Wednesday, 20 April 2016 at 19:18:58 UTC, Minas Mina wrote:

 On Tuesday, 19 April 2016 at 22:28:27 UTC, Alex Parrill wrote:

 I'm proposing that std.experimental.allocator.make, as well as 
 its friends, throw an exception when the allocator cannot 
 satisfy a request instead of returning null.

 [...]


 I believe it was designed this way so that it can be used in 
  nogc code, although I might be wrong.


This is IMO a separate issue: that you cannot easily throw an 
exception without allocating it on the GC heap, making it too 
painful to use in nogc code.

I've heard mentions of altering exception handling to store the 
exception in a static memory space instead of allocating them on 
the heap; I'd much rather see that implemented than the bandage 
solution of ignoring exception handling.
Apr 20 2016
prev sibling parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Tuesday, 19 April 2016 at 22:28:27 UTC, Alex Parrill wrote:

 * It fails faster and safer. It's better to error out 
 immediately with a descriptive "out of memory" message instead 
 of potentially continuing with an invalid pointer and 
 potentially causing an invalid memory access, or worse, a 
 vulnerability, if the developer forgot to check (which is 
 common for boilerplate code).


  Guaranteeing that a returned call from requesting memory does 
make code simpler. I believe Java does this as well (although the 
default memory size wasn't as large as it needed to be :P )

  The downside though is the requirement to throw may not be 
necessary. Having a failed attempt at getting memory and sleeping 
the program for 1-2 seconds before retrying could succeed on a 
future attempt. For games this would be a failure to have the 
entire game pause and hang until it acquires the memory it needs, 
while non critical applications (say compressing data for a 
backup) having it be willing to wait wouldn't be a huge 
disadvantage (assuming it's not at the start and already been 
busy for a while).

  This also heavily depends on what type of memory you're 
allocating. A stack based allocator (with fixed memory) wouldn't 
ever be able to get you more memory than it has fixed in reserve 
so immediately throwing makes perfect sense; Although IF the 
memory could be arranged and a second attempt made before 
deciding to throw could be useful (which assumes not having 
direct pointers to the memory in question and rather having an 
offset which is used. The more I think about it though the less 
likely this would be).
Apr 20 2016
parent reply Alex Parrill <initrd.gz gmail.com> writes:
On Wednesday, 20 April 2016 at 20:23:53 UTC, Era Scarecrow wrote:

  The downside though is the requirement to throw may not be 
 necessary. Having a failed attempt at getting memory and 
 sleeping the program for 1-2 seconds before retrying could 
 succeed on a future attempt. For games this would be a failure 
 to have the entire game pause and hang until it acquires the 
 memory it needs, while non critical applications (say 
 compressing data for a backup) having it be willing to wait 
 wouldn't be a huge disadvantage (assuming it's not at the start 
 and already been busy for a while).


This would be best implemented in a "building block" allocator 
that wraps a different allocator and uses the `allocate` 
function, making it truly optional. It would also need a timeout 
to fail eventually, or else you possibly wait forever.


  This also heavily depends on what type of memory you're 
 allocating. A stack based allocator (with fixed memory) 
 wouldn't ever be able to get you more memory than it has fixed 
 in reserve so immediately throwing makes perfect sense


True, if you are allocating from small pools then OOM becomes 
more likely. But most programs do not directly allocate from 
small pools; rather, they try to allocate from a small pool (ex. 
a freelist) but revert to a larger, slower pool when the smaller 
pool cannot satisfy a request. That is implemented using the 
building block allocators, which use the `allocate` method, not 
`make`.


 Although IF the memory could be arranged and a second attempt 
 made before deciding to throw could be useful (which assumes 
 not having direct pointers to the memory in question and rather 
 having an offset which is used. The more I think about it 
 though the less likely this would be).


This is the mechanism used for "copying" garbage collectors. They 
can only work if they can know about and alter all references to 
the objects that they have allocated, which makes them hard to 
use for languages with raw pointers like D.
Apr 20 2016
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Wednesday, 20 April 2016 at 21:26:12 UTC, Alex Parrill wrote:

 This would be best implemented in a "building block" allocator 
 that wraps a different allocator and uses the 'allocate' 
 function, making it truly optional. It would also need a 
 timeout to fail eventually, or else you possibly wait forever.


  I'd say either you specify the amount of retries, or give some 
amount that would be acceptable for some background program to 
retry for. Say, 30 seconds.


 Although IF the memory could be rearranged and a second 
 attempt made before deciding to throw could be useful


 This is the mechanism used for "copying" garbage collectors. 
 They can only work if they can know about and alter all 
 references to the objects that they have allocated, which makes 
 them hard to use for languages with raw pointers like D.


I was thinking more along the lines of having a slot with the 
memory data and you never take the pointer address, using 
everything through the API. As long as nothing is shared between 
threads and there are no pointers in the data then 
realigning/compacting memory is fine. But then there's a 
potential speed cost if there's a lot to work with.
Apr 20 2016
parent reply Thiez <thiezz gmail.com> writes:
On Thursday, 21 April 2016 at 04:07:52 UTC, Era Scarecrow wrote:

  I'd say either you specify the amount of retries, or give some 
 amount that would be acceptable for some background program to 
 retry for. Say, 30 seconds.


Would that actually be more helpful than simply printing an OOM 
message and shutting down / crashing? Because if the limit is 30 
seconds *per allocation* then successfully allocating, say, 20 
individual objects might take anywhere between 0 seconds and 
almost (but not *quite*) 10 minutes. In the latter case the 
program is still making progress but for the user it would appear 
frozen.
Apr 21 2016
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Thursday, 21 April 2016 at 09:15:05 UTC, Thiez wrote:

 On Thursday, 21 April 2016 at 04:07:52 UTC, Era Scarecrow wrote:

  I'd say either you specify the amount of retries, or give 
 some amount that would be acceptable for some background 
 program to retry for. Say, 30 seconds.


 Would that actually be more helpful than simply printing an OOM 
 message and shutting down / crashing? Because if the limit is 
 30 seconds *per allocation* then successfully allocating, say, 
 20 individual objects might take anywhere between 0 seconds and 
 almost (but not *quite*) 10 minutes. In the latter case the 
 program is still making progress but for the user it would 
 appear frozen.


  Good point. Maybe having a global threshold of 30 seconds while 
it waits and retries every 1/2 second.

  In 30 seconds a lot can change. You can get gigabytes of memory 
freed from other processes and jobs. In the end it really depends 
on the application. A backup utility that you run overnight gives 
you 8+ hours to do the backup that probably takes up to 2 hours 
to actually do. On the other hand no one (sane anyways) wants to 
wait if they are actively using the application and would prefer 
it to die quickly and restart it when there's fewer demands on 
the system.
Apr 21 2016
next sibling parent Alex Parrill <initrd.gz gmail.com> writes:
On Thursday, 21 April 2016 at 13:42:50 UTC, Era Scarecrow wrote:

 On Thursday, 21 April 2016 at 09:15:05 UTC, Thiez wrote:

 On Thursday, 21 April 2016 at 04:07:52 UTC, Era Scarecrow 
 wrote:

  I'd say either you specify the amount of retries, or give 
 some amount that would be acceptable for some background 
 program to retry for. Say, 30 seconds.


 Would that actually be more helpful than simply printing an 
 OOM message and shutting down / crashing? Because if the limit 
 is 30 seconds *per allocation* then successfully allocating, 
 say, 20 individual objects might take anywhere between 0 
 seconds and almost (but not *quite*) 10 minutes. In the latter 
 case the program is still making progress but for the user it 
 would appear frozen.


  Good point. Maybe having a global threshold of 30 seconds 
 while it waits and retries every 1/2 second.

  In 30 seconds a lot can change. You can get gigabytes of 
 memory freed from other processes and jobs. In the end it 
 really depends on the application. A backup utility that you 
 run overnight gives you 8+ hours to do the backup that probably 
 takes up to 2 hours to actually do. On the other hand no one 
 (sane anyways) wants to wait if they are actively using the 
 application and would prefer it to die quickly and restart it 
 when there's fewer demands on the system.


I'm proposing that make throws an exception if the allocator 
cannot satisfy a request (ie allocate returns null). How the 
allocator tries to allocate is it's own business; if it wants to 
sleep (which I don't believe would be helpful outside of 
specialized cases), make doesn't need to care.

Sleeping would be very bad for certain workloads (you mentioned 
games), so having make itself sleep would be inappropriate.
Apr 21 2016
prev sibling parent Thiez <thiezz gmail.com> writes:
On Thursday, 21 April 2016 at 13:42:50 UTC, Era Scarecrow wrote:

 On Thursday, 21 April 2016 at 09:15:05 UTC, Thiez wrote:

 On Thursday, 21 April 2016 at 04:07:52 UTC, Era Scarecrow 
 wrote:

  I'd say either you specify the amount of retries, or give 
 some amount that would be acceptable for some background 
 program to retry for. Say, 30 seconds.


 Would that actually be more helpful than simply printing an 
 OOM message and shutting down / crashing? Because if the limit 
 is 30 seconds *per allocation* then successfully allocating, 
 say, 20 individual objects might take anywhere between 0 
 seconds and almost (but not *quite*) 10 minutes. In the latter 
 case the program is still making progress but for the user it 
 would appear frozen.


  Good point. Maybe having a global threshold of 30 seconds 
 while it waits and retries every 1/2 second.

  In 30 seconds a lot can change. You can get gigabytes of 
 memory freed from other processes and jobs. In the end it 
 really depends on the application. A backup utility that you 
 run overnight gives you 8+ hours to do the backup that probably 
 takes up to 2 hours to actually do. On the other hand no one 
 (sane anyways) wants to wait if they are actively using the 
 application and would prefer it to die quickly and restart it 
 when there's fewer demands on the system.


But background processes might run for months, so having a global 
threshold of 30 seconds combined with a 0.5 second delay between 
retries may result in too few retries in the long run.

So if the retry thing is really the way you want to go you 
probably need to keep track of how many times you've retried 
recently, and then slowly forget about those retries as more time 
passes (time spent waiting for a retry doesn't count). Of course 
this demands additional bookkeeping, but the overhead should be 
acceptable: the 'allocation succeeds' happy path doesn't need to 
know about any of this stuff.

But at the end of the day I would expect the user to be much 
happier if the software simply informs them of insufficient 
memory. The proposed retry scheme would only really have a 
positive effect when the system the software runs on spends a 
significant amount of time flirting with OOM, while never quite 
reaching it to the point where other applications start crashing. 
I think this scenario is very rare/unlikely, and if it occurs the 
user would benefit much more from shutting down some other 
applications, buying more RAM, or (*shudder*) by allowing 
swapping. By silently retrying you are effectively denying the 
user the information they need to solve the actual problem.

Meanwhile, on some operating systems (e.g. Linux) the system will 
happily hand out more memory than it physically possesses, 
because as long as you don't write to that memory it doesn't need 
its own page, so allocations will never return null (for some 
values of 'never', they can still return null if you run out of 
virtual memory, but on a 64-bit system that will realistically 
only happen if you specifically write your program to trigger 
this scenario). Writing to memory can summon the OOM-killer, 
which will kill processes to satisfy its desire to feast on the 
bodies of the fallen. On such a systems attempting to defend 
against allocation returning null seems rather pointless.
Apr 21 2016