www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - new Type[count] takes too much?

reply "Namespace" <rswhite4 googlemail.com> writes:
I'm sure we had already this conversation but I don't find the 
thread.

T[] buffer = new T[N]; assumes more space than stated (in average 
2010 elements more. See: http://dpaste.dzfl.pl/af92ad22c). It 
behaves exactly like reserve and that is IMO wrong. If I reserve 
memory with buffer.reserve(N), I want to have at least N 
elements. That behaviour is correct. But if I use new T[N] I 
mostly want exactly N elements and no extra space.

Thoughts?
Oct 31 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Namespace:


 T[] buffer = new T[N]; assumes more space than stated (in 
 average 2010 elements more. See: 
 http://dpaste.dzfl.pl/af92ad22c). It behaves exactly like 
 reserve and that is IMO wrong. If I reserve memory with 
 buffer.reserve(N), I want to have at least N elements. That 
 behaviour is correct. But if I use new T[N] I mostly want 
 exactly N elements and no extra space.

 Thoughts?


In Python if you append items to an array, it sovra-allocates, 
but if you create an array with the [x] * n syntax, then it 
creates a list (array) exactly of size n.

Bye,
bearophile
Oct 31 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Thursday, 31 October 2013 at 09:27:11 UTC, bearophile wrote:

 Namespace:


 T[] buffer = new T[N]; assumes more space than stated (in 
 average 2010 elements more. See: 
 http://dpaste.dzfl.pl/af92ad22c). It behaves exactly like 
 reserve and that is IMO wrong. If I reserve memory with 
 buffer.reserve(N), I want to have at least N elements. That 
 behaviour is correct. But if I use new T[N] I mostly want 
 exactly N elements and no extra space.

 Thoughts?


 In Python if you append items to an array, it sovra-allocates,


Never heard of 'sovra'. What does it mean?


 but if you create an array with the [x] * n syntax, then it 
 creates a list (array) exactly of size n.

 Bye,
 bearophile


So you agree with me.
Oct 31 2013
parent reply Marco Leise <Marco.Leise gmx.de> writes:
Am Thu, 31 Oct 2013 10:42:35 +0100
schrieb "Namespace" <rswhite4 googlemail.com>:


 On Thursday, 31 October 2013 at 09:27:11 UTC, bearophile wrote:

 In Python if you append items to an array, it sovra-allocates,


 Never heard of 'sovra'. What does it mean?


That's bearophilian for 'over'. :p

-- 
Marco
Oct 31 2013
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 10/31/2013 01:10 PM, Marco Leise wrote:

 Am Thu, 31 Oct 2013 10:42:35 +0100
 schrieb "Namespace" <rswhite4 googlemail.com>:


 On Thursday, 31 October 2013 at 09:27:11 UTC, bearophile wrote:

 In Python if you append items to an array, it sovra-allocates,


 Never heard of 'sovra'. What does it mean?


 That's bearophilian for 'over'. :p


Apparently, a variation of Italian prefix sopra- :)

   http://en.wiktionary.org/wiki/sopra-

Ali
Oct 31 2013
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Oct 31, 2013 at 01:28:13PM -0700, Ali Çehreli wrote:

 On 10/31/2013 01:10 PM, Marco Leise wrote:

Am Thu, 31 Oct 2013 10:42:35 +0100
schrieb "Namespace" <rswhite4 googlemail.com>:


On Thursday, 31 October 2013 at 09:27:11 UTC, bearophile wrote:

In Python if you append items to an array, it sovra-allocates,


Never heard of 'sovra'. What does it mean?


That's bearophilian for 'over'. :p


 
 Apparently, a variation of Italian prefix sopra- :)
 
   http://en.wiktionary.org/wiki/sopra-


[...]

http://en.wiktionary.org/wiki/sovra

:)


T

-- 
Nearly all men can stand adversity, but if you want to test a man's character,
give him power. -- Abraham Lincoln
Oct 31 2013
prev sibling next sibling parent reply "safety0ff" <safety0ff.dev gmail.com> writes:
On Thursday, 31 October 2013 at 09:15:53 UTC, Namespace wrote:

 I'm sure we had already this conversation but I don't find the 
 thread.

 T[] buffer = new T[N]; assumes more space than stated (in 
 average 2010 elements more. See: 
 http://dpaste.dzfl.pl/af92ad22c). It behaves exactly like 
 reserve and that is IMO wrong. If I reserve memory with 
 buffer.reserve(N), I want to have at least N elements. That 
 behaviour is correct. But if I use new T[N] I mostly want 
 exactly N elements and no extra space.

 Thoughts?


To me it looks like it is derived directly from the way the GC 
allocates chunks:
Next power of two if less than 4096 otherwise some multiple of 
4096.

Unless you modify the GC, this behaviour is present whether you 
can see it or not (http://dpaste.dzfl.pl/5481ffc2 .)
Oct 31 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Thursday, 31 October 2013 at 09:48:23 UTC, safety0ff wrote:

 On Thursday, 31 October 2013 at 09:15:53 UTC, Namespace wrote:

 I'm sure we had already this conversation but I don't find the 
 thread.

 T[] buffer = new T[N]; assumes more space than stated (in 
 average 2010 elements more. See: 
 http://dpaste.dzfl.pl/af92ad22c). It behaves exactly like 
 reserve and that is IMO wrong. If I reserve memory with 
 buffer.reserve(N), I want to have at least N elements. That 
 behaviour is correct. But if I use new T[N] I mostly want 
 exactly N elements and no extra space.

 Thoughts?


 To me it looks like it is derived directly from the way the GC 
 allocates chunks:
 Next power of two if less than 4096 otherwise some multiple of 
 4096.

 Unless you modify the GC, this behaviour is present whether you 
 can see it or not (http://dpaste.dzfl.pl/5481ffc2 .)


Maybe (and hopefully) I'm wrong, but it seems that the static 
array is on the heap?
Oct 31 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, October 31, 2013 10:59:48 Namespace wrote:

 On Thursday, 31 October 2013 at 09:48:23 UTC, safety0ff wrote:

 On Thursday, 31 October 2013 at 09:15:53 UTC, Namespace wrote:

 I'm sure we had already this conversation but I don't find the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in
 average 2010 elements more. See:
 http://dpaste.dzfl.pl/af92ad22c). It behaves exactly like
 reserve and that is IMO wrong. If I reserve memory with
 buffer.reserve(N), I want to have at least N elements. That
 behaviour is correct. But if I use new T[N] I mostly want
 exactly N elements and no extra space.
 
 Thoughts?


 
 To me it looks like it is derived directly from the way the GC
 allocates chunks:
 Next power of two if less than 4096 otherwise some multiple of
 4096.
 
 Unless you modify the GC, this behaviour is present whether you
 can see it or not (http://dpaste.dzfl.pl/5481ffc2 .)


 
 Maybe (and hopefully) I'm wrong, but it seems that the static
 array is on the heap?


T[] buffer = new T[N];

is a dynamic array. Now, in the code in your dpaste link, you have a static 
array which is in a struct which is on the heap, so that's different, but now 
you're dealing with the amount of memory that gets allocated on the heap for 
the struct, and as the GC is going to allocate in multiples of 2, more than 
the size of the struct is going to be allocated. It might be that some of the 
memory beyond the end of the struct might actually be used for another object 
rather than the struct using the memory block by itself (I'm not sure what the 
GC does in that regard), but it's definitely going to allocate in multiples of 
2, so if the GC has to go up another multiple of 2 to make the struct fit, 
it'll go up another multiple of 2.

- Jonathan M Davis
Oct 31 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Thursday, 31 October 2013 at 10:12:10 UTC, Jonathan M Davis 
wrote:

 On Thursday, October 31, 2013 10:59:48 Namespace wrote:

 On Thursday, 31 October 2013 at 09:48:23 UTC, safety0ff wrote:

 On Thursday, 31 October 2013 at 09:15:53 UTC, Namespace 
 wrote:

 I'm sure we had already this conversation but I don't find 
 the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in
 average 2010 elements more. See:
 http://dpaste.dzfl.pl/af92ad22c). It behaves exactly like
 reserve and that is IMO wrong. If I reserve memory with
 buffer.reserve(N), I want to have at least N elements. That
 behaviour is correct. But if I use new T[N] I mostly want
 exactly N elements and no extra space.
 
 Thoughts?


 
 To me it looks like it is derived directly from the way the 
 GC
 allocates chunks:
 Next power of two if less than 4096 otherwise some multiple 
 of
 4096.
 
 Unless you modify the GC, this behaviour is present whether 
 you
 can see it or not (http://dpaste.dzfl.pl/5481ffc2 .)


 
 Maybe (and hopefully) I'm wrong, but it seems that the static
 array is on the heap?


 T[] buffer = new T[N];

 is a dynamic array. Now, in the code in your dpaste link, you 
 have a static
 array which is in a struct which is on the heap, so that's 
 different, but now
 you're dealing with the amount of memory that gets allocated on 
 the heap for
 the struct, and as the GC is going to allocate in multiples of 
 2, more than
 the size of the struct is going to be allocated. It might be 
 that some of the
 memory beyond the end of the struct might actually be used for 
 another object
 rather than the struct using the memory block by itself (I'm 
 not sure what the
 GC does in that regard), but it's definitely going to allocate 
 in multiples of
 2, so if the GC has to go up another multiple of 2 to make the 
 struct fit,
 it'll go up another multiple of 2.

 - Jonathan M Davis


Hm, seems not very performant for a *system* language. But fine, 
thanks for your explanation. :)
Oct 31 2013
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, October 31, 2013 11:16:35 Namespace wrote:

 Hm, seems not very performant for a *system* language. But fine,
 thanks for your explanation. :)


I believe that C's malloc does the same thing.

- Jonathan M Davis
Oct 31 2013
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, October 31, 2013 10:15:51 Namespace wrote:

 I'm sure we had already this conversation but I don't find the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in average
 2010 elements more. See: http://dpaste.dzfl.pl/af92ad22c). It
 behaves exactly like reserve and that is IMO wrong. If I reserve
 memory with buffer.reserve(N), I want to have at least N
 elements. That behaviour is correct. But if I use new T[N] I
 mostly want exactly N elements and no extra space.
 
 Thoughts?


You're making the assumption that it would be normal to not want to then 
append to something you allocated with new T[N], and I don't think that that's 
a valid assumption. Also, from what I understand of how allocators work, they 
normally grab memory in sizes which are a multiple of 2, so I would expect it 
to be highly abnormal to ever get exactly the amount of memory that you 
requested. You're pretty much always going to get extra.

- Jonathan M Davis
Oct 31 2013
next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Thu, 31 Oct 2013 02:52:49 -0700
schrieb Jonathan M Davis <jmdavisProg gmx.com>:


 On Thursday, October 31, 2013 10:15:51 Namespace wrote:

 I'm sure we had already this conversation but I don't find the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in average
 2010 elements more. See: http://dpaste.dzfl.pl/af92ad22c). It
 behaves exactly like reserve and that is IMO wrong. If I reserve
 memory with buffer.reserve(N), I want to have at least N
 elements. That behaviour is correct. But if I use new T[N] I
 mostly want exactly N elements and no extra space.
 
 Thoughts?




Maybe run a comparison with another popular GC enabled
language and check the memory use to find pathological cases.
I'd assume that D's GC doesn't waste more memory than any
other for dynamic arrays.


 You're making the assumption that it would be normal to not want to then 
 append to something you allocated with new T[N], and I don't think that that's 
 a valid assumption.


That doesn't happen much in my programming practice. I'm with
the OP on this.


 Also, from what I understand of how allocators work, they 
 normally grab memory in sizes which are a multiple of 2, so I would expect it 
 to be highly abnormal to ever get exactly the amount of memory that you 
 requested. You're pretty much always going to get extra.
 
 - Jonathan M Davis


That's true. Although now I wonder if you could gain anything
from having memory pages split into chunks of T.sizeof from
which you can allocate single objects or whole arrays of T
with a compact layout...

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T[6]       |T|T|           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

-- 
Marco
Oct 31 2013
prev sibling parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Thursday, 31 October 2013 at 09:53:39 UTC, Jonathan M Davis 
wrote:

 On Thursday, October 31, 2013 10:15:51 Namespace wrote:

 I'm sure we had already this conversation but I don't find the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in 
 average
 2010 elements more. See: http://dpaste.dzfl.pl/af92ad22c). It
 behaves exactly like reserve and that is IMO wrong. If I 
 reserve
 memory with buffer.reserve(N), I want to have at least N
 elements. That behaviour is correct. But if I use new T[N] I
 mostly want exactly N elements and no extra space.
 
 Thoughts?


 You're making the assumption that it would be normal to not 
 want to then
 append to something you allocated with new T[N], and I don't 
 think that that's
 a valid assumption.


I disagree. If I want to append I use reserve and I think that is 
the most common approach.
Oct 31 2013
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, October 31, 2013 23:06:22 Namespace wrote:

 On Thursday, 31 October 2013 at 09:53:39 UTC, Jonathan M Davis
 
 wrote:

 On Thursday, October 31, 2013 10:15:51 Namespace wrote:

 I'm sure we had already this conversation but I don't find the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in
 average
 2010 elements more. See: http://dpaste.dzfl.pl/af92ad22c). It
 behaves exactly like reserve and that is IMO wrong. If I
 reserve
 memory with buffer.reserve(N), I want to have at least N
 elements. That behaviour is correct. But if I use new T[N] I
 mostly want exactly N elements and no extra space.
 
 Thoughts?


 
 You're making the assumption that it would be normal to not
 want to then
 append to something you allocated with new T[N], and I don't
 think that that's
 a valid assumption.


 
 I disagree. If I want to append I use reserve and I think that is
 the most common approach.


I would fully expect that most people don't bother with reserve or capacity 
and that they simply create the array at whatever size they create it at and 
then append to it without worrying about reserve. But we'd have to get real 
data on that to know for sure one way or the other.

Certainly, most folks who are focusing on append performance seem to use 
Appender, and for the most part, I would suggest that anyone using reserve 
should be using Appender instead.

- Jonathan M Davis
Oct 31 2013
parent reply "Namespace" <rswhite4 googlemail.com> writes:
On Thursday, 31 October 2013 at 23:48:19 UTC, Jonathan M Davis 
wrote:

 On Thursday, October 31, 2013 23:06:22 Namespace wrote:

 On Thursday, 31 October 2013 at 09:53:39 UTC, Jonathan M Davis
 
 wrote:

 On Thursday, October 31, 2013 10:15:51 Namespace wrote:

 I'm sure we had already this conversation but I don't find 
 the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in
 average
 2010 elements more. See: http://dpaste.dzfl.pl/af92ad22c). 
 It
 behaves exactly like reserve and that is IMO wrong. If I
 reserve
 memory with buffer.reserve(N), I want to have at least N
 elements. That behaviour is correct. But if I use new T[N] I
 mostly want exactly N elements and no extra space.
 
 Thoughts?


 
 You're making the assumption that it would be normal to not
 want to then
 append to something you allocated with new T[N], and I don't
 think that that's
 a valid assumption.


 
 I disagree. If I want to append I use reserve and I think that 
 is
 the most common approach.


 I would fully expect that most people don't bother with reserve 
 or capacity
 and that they simply create the array at whatever size they 
 create it at and
 then append to it without worrying about reserve. But we'd have 
 to get real
 data on that to know for sure one way or the other.

 Certainly, most folks who are focusing on append performance 
 seem to use
 Appender, and for the most part, I would suggest that anyone 
 using reserve
 should be using Appender instead.

 - Jonathan M Davis


Currently Appender isn't more performant than built-in arrays. ;)
Oct 31 2013
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, November 01, 2013 01:16:53 Namespace wrote:

 Currently Appender isn't more performant than built-in arrays. ;)


If Appender is not more performant for appending than just appending to a 
naked array, then something is very wrong with Appender, because it's whole 
job is to make sure that it calls all of the appropriate functions on its 
internal array which it needs to in order to make appending efficient (e.g. 
assumeSafeAppend).

- Jonathan M Davis
Nov 01 2013
prev sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 1 November 2013 at 00:16:55 UTC, Namespace wrote:

 On Thursday, 31 October 2013 at 23:48:19 UTC, Jonathan M Davis 
 wrote:

 On Thursday, October 31, 2013 23:06:22 Namespace wrote:

 On Thursday, 31 October 2013 at 09:53:39 UTC, Jonathan M Davis
 
 wrote:

 On Thursday, October 31, 2013 10:15:51 Namespace wrote:

 I'm sure we had already this conversation but I don't find 
 the
 thread.
 
 T[] buffer = new T[N]; assumes more space than stated (in
 average
 2010 elements more. See: http://dpaste.dzfl.pl/af92ad22c). 
 It
 behaves exactly like reserve and that is IMO wrong. If I
 reserve
 memory with buffer.reserve(N), I want to have at least N
 elements. That behaviour is correct. But if I use new T[N] 
 I
 mostly want exactly N elements and no extra space.
 
 Thoughts?


 
 You're making the assumption that it would be normal to not
 want to then
 append to something you allocated with new T[N], and I don't
 think that that's
 a valid assumption.


 
 I disagree. If I want to append I use reserve and I think 
 that is
 the most common approach.


 I would fully expect that most people don't bother with 
 reserve or capacity
 and that they simply create the array at whatever size they 
 create it at and
 then append to it without worrying about reserve. But we'd 
 have to get real
 data on that to know for sure one way or the other.

 Certainly, most folks who are focusing on append performance 
 seem to use
 Appender, and for the most part, I would suggest that anyone 
 using reserve
 should be using Appender instead.

 - Jonathan M Davis


 Currently Appender isn't more performant than built-in arrays. 
 ;)


I have found it more performant. A sensible test case where it is 
slower should be filed as a bug.
Nov 01 2013
parent "Namespace" <rswhite4 googlemail.com> writes:
It is. I don't know if it is fixed already, and I don't have the 
time to search for the thread. But afaik monarch filled the bug.
Nov 01 2013