www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sort trouble

reply bearophile <bearophileHUGS lycos.com> writes:
This little program gives me an "Error: Access Violation" on Windows, v1.042:

import std.random: rand;
void main() {
    auto a = new uint[10_000_000];
    for (int i = 0; i < a.length; i++)
        a[i] = rand();
    a.sort;
    a.sort;
}

Can someone confirm this?

Bye,
bearophile
Apr 07 2009
parent reply bearophile <bearophileHUGS lycos.com> writes:
Even just:

void main() {
    auto a = new uint[10_000_000];
    a.sort;
    a.sort;
}

Bye,
bearophile
Apr 07 2009
next sibling parent reply Don <nospam nospam.com> writes:
bearophile wrote:

 Even just:
 
 void main() {
     auto a = new uint[10_000_000];
     a.sort;
     a.sort;
 }
 
 Bye,
 bearophile



Confirmed. In fact, any size below 0x8F_FFFF works,
and any size >= 0x8F_FFFF fails. On DMD2.027 as well.

void main() {
     auto a = new uint[0x8F_FFFF]; // smallest size that fails
     a.sort;
     a.sort;
}
Apr 07 2009
next sibling parent Don <nospam nospam.com> writes:
Don wrote:

 bearophile wrote:

 Even just:

 void main() {
     auto a = new uint[10_000_000];
     a.sort;
     a.sort;
 }

 Bye,
 bearophile



 Confirmed. In fact, any size below 0x8F_FFFF works,
 and any size >= 0x8F_FFFF fails. On DMD2.027 as well.
 
 void main() {
     auto a = new uint[0x8F_FFFF]; // smallest size that fails
     a.sort;
     a.sort;
 }



   byte*[40] stack;              // stack

in
extern (C) long _adSort(Array a, TypeInfo ti)
in qsort.d.
Apr 07 2009
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Smaller version, one sort is enough to cause the error:

void main() {
  auto a = new uint[0x8F_FFFF]; // smallest size that fails
  a.sort;
}

I like the idea of having a built-in sort, but I think it's now better to
remove it, and move it into the std lib, so:
- It can be replaced/improved/debugged in a simpler way.
- It can be more flexible (for example mine accepts an optional "key" mapping
function)
- It can be a template, so it can be faster (confirmed. I have a sort that is
sometimes 3+ times faster).
- The overall size and complexity of the language can be a bit lower.
- The usage syntax can be almost the same anyway: arr.sort()

Bye,
bearophile
Apr 07 2009
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
bearophile wrote:
<snip>

 - It can be more flexible (for example mine accepts an optional "key" mapping
function)



What is there preventing a built-in sort being implemented to do this?


 - It can be a template, so it can be faster (confirmed. I have a sort that is
sometimes 3+ times faster).




What is there preventing a built-in sort being implemented in this way?

Stewart
Apr 07 2009
next sibling parent Don <nospam nospam.com> writes:
Stewart Gordon wrote:

 bearophile wrote:
 <snip>

 - It can be more flexible (for example mine accepts an optional "key" 
 mapping function)



 What is there preventing a built-in sort being implemented to do this?



It's more difficult than doing it in a library. For apparently no 
benefit at all.


 

 - It can be a template, so it can be faster (confirmed. I have a sort 
 that is sometimes 3+ times faster).



 
 What is there preventing a built-in sort being implemented in this way?
 
 Stewart
Apr 07 2009
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Stewart Gordon:

 - It can be a template, so it can be faster (confirmed. I have a sort that is
sometimes 3+ times faster).






Can you use templates with a statically compiled std lib?

Bye,
bearophile
Apr 07 2009
parent bearophile <bearophileHUGS lycos.com> writes:
Jarrett Billingsley:

 The other problem with a templated sort is that while it's faster than
 the current built-in sort, it also means there would be a different
 template instantiation for every element type.  Not ideal.



So far it was not a problem for me.

Bye,
bearophile
Apr 08 2009
prev sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Tue, Apr 7, 2009 at 7:08 PM, bearophile <bearophileHUGS lycos.com> wrote:

 Stewart Gordon:

 - It can be a template, so it can be faster (confirmed. I have a sort that is
sometimes 3+ times faster).






 Can you use templates with a statically compiled std lib?



The template would have to be in the "headers."  It wouldn't be
compiled into the library file itself.

The other problem with a templated sort is that while it's faster than
the current built-in sort, it also means there would be a different
template instantiation for every element type.  Not ideal.
Apr 07 2009