On 9/23/13 1:32 PM, Timon Gehr wrote:
> One issue you will probably run into and maybe want to fix in some way
> during the typed allocator design is that private constructors cannot be
> called from templates parameterized on types.

Hrm, that's a real problem. We've ran into it at work when we were trying to replace a macro with a template. The macro is automatically friend with everyone! :o)

> Is there an intention to also support replacements of instance new
> allocations, i.e. object.new subobject(args)?

It's a good point to keep in mind as we move further with this.


Andrei

On 9/23/13 1:37 PM, Peter Alexander wrote:
> What if, for example, I wanted to allocate a 4096 byte aligned block
> from the GC allocator? Do I have to create a new allocator backed by the
> GC allocator?

I've been thinking a good library component would be AlignmentAllocator that would work like this:

struct AlignmentAllocator(Allocator, size_t desiredAlignment)
if (Allocator.alignment < desiredAlignment)
{
    enum alignment = desiredAlignment;
    ...
}

That allocator would allocate more memory (I suspect there's a gcd calculation somewhere :o)) and then adjust the starting pointer of the allocated block to reach the requested alignment.

I'm just off the phone with Walter discussing this and related issue. It's an interesting problem space.

> What if the alignment is not known at compile time (e.g. hard disk page
> size or CPU cache line size)?

The proposed design assumes compile-time allocation sizes. A trick similar to the one above (overallocate and adjust pointer) should work.

I'd need a handful of good examples where the alignment must be known at runtime. Can you link to some?

> Might be better to pass the desired alignment in the allocate method.

The thing is in 99%+ of the cases you don't need it. Then perhaps in 99%+ of the remaining cases the alignment is known during compilation. Nevertheless it's a change worth investigating.

>> * available is a property that returns how many total (not necessarily
>> contiguous) bytes are available for allocation. The NullAllocator
>> knows statically it has 0 bytes available so it implements it as an
>> enum. Generally allocators will implement it as a @property. This
>> property is optional.
>
> It would be useful to know the maximum available contiguous block size
> too, so that you can find out if an allocation will succeed without
> calling allocate.

I think the best way is to just go ahead and attempt an allocation, especially if the allocator is shared (races!). (There's some flexibility with expand() there, which has a minimum size and a desired size.) But clearly the information of the largest contiguous block is currently missing, and is reasonable to be considered for addition.

> It's also useful for diagnosing fragmentation issues
> e.g. "allocation failed, free memory = X, max contiguous = Y". If X is
> high and Y is low then you are highly fragmented.
>
> Of course, this should be optional.

Makes sense.

>> * allocate(s) returns a ubyte[] with length at least s, or null. (It
>> does not throw on out-of-memory because that would hurt composability;
>> it turns out many elemental allocators do naturally run out of
>> memory.) This method is required for all allocators. In most
>> allocators this method should be @safe.
>
> What are the semantics of allocate(0)? malloc(0) is implementation defined.

I defined Mallocator to return whatever malloc returns on allocate(0), but decided realloc() is too messed up and special-cased reallocate(0) to free memory and place null in the buffer. Probably I'll work the same logic in Mallocator.allocate(0) to eliminate platform dependencies.


Andrei

On 9/23/2013 1:18 PM, Andrei Alexandrescu wrote:
> Does void[] make any promise about alignment?

No.

On Monday, 23 September 2013 at 21:27:36 UTC, Andrei Alexandrescu wrote:
> That allocator would allocate more memory (I suspect there's a gcd calculation somewhere :o)) and then adjust the starting pointer of the allocated block to reach the requested alignment.

That's quite an inefficient use of memory for large alignment sizes.

Also, how does it work with your deallocate interface? Suppose I request an 0x100 aligned block of 0x100 bytes. Your alignment allocator requests 0x200 from the GC, which maybe returns [0xffff0040-0xffff0240] and then returns an aligned buffer from that [0xffff0100-0xffff0200]. Later, I try to deallocate that buffer, which means your alignment allocator has to deallocate the original buffer. Where does the alignment allocator store the original GC-provided buffer ptr + size? It cannot be determined from the buffer I gave it.


> I'd need a handful of good examples where the alignment must be known at runtime. Can you link to some?

mprotect requires a pointer that is a multiple of the system page size, which isn't constant.

http://linux.die.net/man/2/mprotect


Reading a file without buffering on Windows requires that you align the destination buffer on volume sector size boundaries, which is not known at compile time (although many just assume 4096).

http://msdn.microsoft.com/en-us/library/windows/desktop/cc644950(v=vs.85).aspx


As I mentioned previously, you may want to also align to the cache line size (for performance). This is not known at compile time (although again, is often assumed in practice).

On 9/23/13 3:12 PM, Peter Alexander wrote:
> On Monday, 23 September 2013 at 21:27:36 UTC, Andrei Alexandrescu wrote:
>> That allocator would allocate more memory (I suspect there's a gcd
>> calculation somewhere :o)) and then adjust the starting pointer of the
>> allocated block to reach the requested alignment.
>
> That's quite an inefficient use of memory for large alignment sizes.

I don't see a way around it unless the allocator natively provides a large alignment size, which it would then advertise in its "alignment" constant. The problem is independent of this particular design.

> Also, how does it work with your deallocate interface? Suppose I request
> an 0x100 aligned block of 0x100 bytes. Your alignment allocator requests
> 0x200 from the GC, which maybe returns [0xffff0040-0xffff0240] and then
> returns an aligned buffer from that [0xffff0100-0xffff0200]. Later, I
> try to deallocate that buffer, which means your alignment allocator has
> to deallocate the original buffer. Where does the alignment allocator
> store the original GC-provided buffer ptr + size? It cannot be
> determined from the buffer I gave it.

Walter noted the same issue. I'd need to think about it. A simple solution is to simply store the size just before the pointer returned, in a dope block manner.

>> I'd need a handful of good examples where the alignment must be known
>> at runtime. Can you link to some?
>
> mprotect requires a pointer that is a multiple of the system page size,
> which isn't constant.
>
> http://linux.die.net/man/2/mprotect

Thanks! I see posix_memalign is a corresponding call that returns a page-aligned chunk of memory. I assume calls like mmap also return page-aligned chunks. Indeed it is a problem for the current design that the alignment must be known during compilation.

> Reading a file without buffering on Windows requires that you align the
> destination buffer on volume sector size boundaries, which is not known
> at compile time (although many just assume 4096).
	>
> http://msdn.microsoft.com/en-us/library/windows/desktop/cc644950(v=vs.85).aspx

I see there's a difference between x86 and Itanium in page size...

I'm trying to lean toward handling these as rare/exotic cases without outright eliminating them, while providing simple and efficient handling of alignment for the frequent cases (i.e. allocate ints at addresses multiple of 4 etc).

> As I mentioned previously, you may want to also align to the cache line
> size (for performance). This is not known at compile time (although
> again, is often assumed in practice).

Indeed.


Andrei

On Mon, 23 Sep 2013 17:02:09 +0200
"Adam D. Ruppe" <destructionator@gmail.com> wrote:

> We should really deprecate the new keyword. It'd break like all code ever, but with D's templates, there's no need for it, and when it is there, it is going to spark problems about replacing global allocators or the library allocators being second class citizens.
> 

I think that's addressing the wrong problem, it wouldn't solve much, if anything. We'd just end up with a lot of lib writers (and others) hardcoding in usage of the default allocator. So it'd be exactly the same as now, just with uglier syntax and a ton of breakage.

What's ultimately needed is a way to change the default allocator for not only "new" but also array concatenation, closures, and any other part of the language that might allocate. That way, we actually *do* get the benefits we're looking for, plus we keep the nicer current syntax and no breakage.

tl;dr: "new" is a red herring. The real issue is being able to easily replace the default allocator.

On Sun, 22 Sep 2013 16:49:57 -0700
Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> 
> * expand(b, minDelta, maxDelta) grows b's length by at least minDelta (and on a best-effort basis by at least maxDelta)

Minor bikeshedding issue, but 'maxDelta' isn't a maximum at
all by your description, rather a suggested-but-optional minimum. So it
shouldn't be called 'maxDelta' - very misleading. Should be something
like 'preferredDelta' or 'idealMinDelta', etc.

On Mon, Sep 23, 2013 at 07:29:39PM -0400, Nick Sabalausky wrote:
> On Mon, 23 Sep 2013 17:02:09 +0200
> "Adam D. Ruppe" <destructionator@gmail.com> wrote:
> 
> > We should really deprecate the new keyword. It'd break like all code ever, but with D's templates, there's no need for it, and when it is there, it is going to spark problems about replacing global allocators or the library allocators being second class citizens.
> > 
> 
> I think that's addressing the wrong problem, it wouldn't solve much, if anything. We'd just end up with a lot of lib writers (and others) hardcoding in usage of the default allocator. So it'd be exactly the same as now, just with uglier syntax and a ton of breakage.
> 
> What's ultimately needed is a way to change the default allocator for not only "new" but also array concatenation, closures, and any other part of the language that might allocate. That way, we actually *do* get the benefits we're looking for, plus we keep the nicer current syntax and no breakage.
> 
> tl;dr: "new" is a red herring. The real issue is being able to easily replace the default allocator.

I thought Walter's DIP already addresses the issue of replacing the default allocator?

	http://wiki.dlang.org/DIP46

I get the feeling that we don't have a good handle on the fundamental issues, though. Having a stack for managing the default allocator works for the simpler cases, but it's unclear how things would interact once you throw in other requirements, like class/struct-scoped allocators, block scoped allocators inside closures, user-specified allocators that must interact with the foregoing, etc..

For example, it's relatively easy to understand this:

	void doWork() {
		gc_push(MyAlloc);
		scope(exit) gc_pop();
		... // do work
	}
	void doMoreWork() {
		gc_push(AnotherAlloc);
		scope(exit) gc_pop();
		... // do work
	}
	void main() {
		doWork();
		doMoreWork();
	}

But once you throw in closures and delegates, things become rather murky:

	auto getCallback() {
		gc_push(MyAlloc);
		scope(exit) gc_pop();

		int closed_var;
		return {
			// What does this do?
			closed_var++;

			string x = "abc";
			x ~= "def"; // which allocator does this use?
		};
	}
	void main() {
		auto dg = getCallback();
		gc_push(OtherAlloc);
		scope(exit) gc_pop();
		dg();		// Hmm...
	}


T

-- 
May you live all the days of your life. -- Jonathan Swift

On Monday, 23 September 2013 at 17:16:40 UTC, Andrei Alexandrescu wrote:
> The singleton allocator "it" is instrumental for supporting stateful and stateless allocators with ease. It took me a few iterations to get to that, and I'm very pleased with the results. I think it would be difficult to improve on it without making other parts more difficult.
>

The allocator can use a singleton internally without using "it". I'm unclear what is the problem solved.

>> What you call safe really isn't. Allocate something on the GC, store a
>> pointer on a custom allocated location, collect, enjoy the memory
>> corruption.
>
> I don't understand this. There are no pointers at this level, only untyped memory. The main chance of corruption is to access something after it's been freed.
>

If there are no pointers at this level, then the collect method do not make any sense.

>> Allocation can only be safe if the GRAND MASTER GC is aware of it.
>
> I don't think so.
>

When GRAND MASTER GC unhappy, he free live objects.

On Monday, 23 September 2013 at 20:18:56 UTC, Andrei Alexandrescu wrote:
> On 9/23/13 1:04 PM, Walter Bright wrote:
>> On 9/23/2013 10:08 AM, Andrei Alexandrescu wrote:
>>> I'm unclear on what void[] means starting from its semantics.
>>
>> I agree that it should be void[], as that represents (in D) a block of
>> untyped data. void[] should be ideal for a primitive allocator.
>
> Great, made that change, it all works. Does void[] make any promise about alignment?
>
> Andrei

void[] dont make any promise about anything, that is the whole point.