ex:
Welcome to D :-) Few more comments beside the ones written by Jonathan M Davis.
> I'm learning D and I was wondering on what can be optimized of my
> implementation of a palindrome function:
See below.
> 2) Does using a variable to store the string length is more efficient than
> calling the length method?
Nope. When you have similar questions you can write a small benchmark and you
can take a look at the produced assembly code.
> 4) Is some way to declare the nested functions at the end, this way I could
> create nice "routines" of a function.
I don't understand this question. But inside a function the names need to be
written in their natural visibility order, so you have to define nested
functions before you use them.
> 5) I could not find in the documentation if when I declare a variable inside a
> block (a loop for example) that variable creation is optimized by the
> compiler.
With DMD sometimes the compiler is able to pull it out of the loop, and some
other times it's not able to do it. Generally in the simple cases DMD is able
to do it. But I have seen were updating an object field inside a method was not
pulled out of the loop and was not replaced by a temporary variable by the DMD
compiler. LDC (D1) compiler is usually better in this regard. So if you have a
performance critical routine it's better to manually move all things out of the
loop :-)
> Sorry I forg to paste my last version"
>
> bool isPalindrome(int num) {
> string s = text(num);
> int length = s.length;
> int limit = length / 2;
> for (int i = 0; i < limit; ++i) {
> if (s[i] != s[$ - 1 - i]) {
> return false;
> }
> }
> return true;
> }
D is a multi-level language, so usually there are always ways to further
optimize code. At the end you can even translate your routine in inlined
assembly. Often you don't need to write the faster code, a more natural
implementation is enough. Idiomatic D style is often not the most efficient way
to write your code, so if you look for max efficiency, you end with code that
is often not idiomatic.
This is written in C-style, and seems faster:
import std.c.stdio: sprintf;
import std.c.stdlib: exit, EXIT_FAILURE;
size_t isPalindrome(int num) {
if (num == int.min) // because you can't negate int.min
return 0;
if (num < 0)
num = -num;
char[20] s = void;
char* inf = s.ptr;
int size = sprintf(inf, "%d", num); // atoi is faster
if (size < 0)
exit(EXIT_FAILURE); // or you can return 2 as error code
char* sup = &(s[size - 1]);
while (inf < sup)
// you can add a loop invariant test here
if (*inf++ != *sup--)
return 0;
return 1;
}
void main() {
assert(isPalindrome(0));
assert(!isPalindrome(10));
assert(isPalindrome(101));
assert(!isPalindrome(1010));
assert(isPalindrome(-1));
assert(isPalindrome(-101));
assert(isPalindrome(1234554321));
assert(isPalindrome(123454321));
}
This function allocates the string on the stack to avoid heap activity, returns
a word because it's sometimes more efficient than fiddling with a byte type
(the bool).
But it's not the fastest possible you can write, even if you don't touch
assembly, because sprintf() is not the most efficient here, you can write your
own faster atoi in D:
size_t isPalindrome(int num) {
if (num == int.min) // because you can't negate int.min
return 0;
if (num < 0)
num = -num;
int[20] snum = void;
int* inf = snum.ptr;
int* sup = inf;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
if (!num) goto END; *sup++ = num % 10; num /= 10;
END:
sup--;
while (inf < sup)
if (*inf++ != *sup--)
return 0;
return 1;
}
void main() {
assert(isPalindrome(0));
assert(isPalindrome(5));
assert(!isPalindrome(10));
assert(isPalindrome(101));
assert(!isPalindrome(1010));
assert(isPalindrome(-1));
assert(isPalindrome(-101));
assert(isPalindrome(1234554321));
assert(isPalindrome(123454321));
assert(!isPalindrome(int.max));
}
But DMD is not good at coverting %10 and /10 in shifts and the like as better
compilers are able to do, so such code fiddly code ends slower than the version
with sprintf(). If compiled with LDC this latest version can be faster than the
version with sprintf.
In normal D programs you never write code like that unless your profiler has
shown you finding the palindrome is time-critical in your program, and even
then you may start thinking about 1/2 GB of RAM to pre-compute all palindromes
of 32-bit inputs (keeping one bit for each answer), but this is not nice for
the CPU caches, so tests and timings are needed.
Bye,
bearophile
