Change representation of dynamic arrays?

[Janice Caron]

On 10/20/07, David Brown <dlang at davidb.org> wrote:
> On Sat, Oct 20, 2007 at 04:44:06PM +0100, Janice Caron wrote:
>
> For any constant division, there is an equivalent multiplication
> that will give the same result.

I hadn't thought about that before, but yes, you're right. The rule
is, if two numbers a and b are relatively prime (that is to say:
gcd(a,b)=1) there is exactly one number c=inv(a) mod b so that c*a mod
b=1. So for what you suggest, b would have to be 2^32 (that is,
uint.max+1) and a the number you want to divide by. In order to be
coprime with b, a may /not/ be even, but that's not a problem because
we can just do shifts until it isn't. So, for example, to divide by 7,
you can just multiply by invmod(7,0x100000000). To divide by 14, you'd
right-shift first, and then divide by 7. Cool!

I wonder if D actually does things this way?


> However, (array.length == 0) is a real easy thing for an optimizer to see.
> It certainly doesn't justify adding a special construct to the language for
> it.

I was thinking ahead. I was assuming we'd want the same semantics for
all collections, not just arrays. C++ STL has an empty() function as
well as a size() function for exactly that reason. For some
collections, calculating .length() will be an O(N) operation, so for
those collections, an isEmpty() functions would make sense. I agree
it's less necessary for a plain old array, but it would help template
metaprogramming enormously if something like isEmpty was available, so
you wouldn't need to know what kind of collection you were dealing
with.

That said, it's easy enough to add as a standalone function if it's
not built in.