Hi,

In one of my project, I have to call IntToStr more than 10M times. I noticed that IntToStr calls Str function. I implemented my own version of IntToStr which is almost twice faster than the current implementation of IntToStr. I wonder if it is possible to use my code in IntToStr function.

I attached my function, and also a sample code which calls MyIntToStr and IntToStr 1000 times. I used valgrind to compare the performance of the two function.

Amir
P.S. I understand that my code is not easy to read/understand, but the question is, should the code for a library be readable/easy to understand?

P.S. I compiled the project using
fpc -Sd -O3 IntToStr.lpr

Check the attachments on this email.

Amir

There are 4 generic routines in "./FPC_SRC/rtl/inc/generic.inc":

 procedure int_str(l:longint;out s:shortstring);
 procedure int_str_unsigned(l:longword;out s:shortstring);
 procedure int_str(l:int64;out s:shortstring);
 procedure int_str_unsigned(l:qword;out s:shortstring);

And also an i386-speciic assembler variants in "./FPC_SRC/rtl/i386/i386.inc", which I suspect use approach similar to yours, but I'm not sure they are "enabled"..

{$if defined(disabled) and defined(regcall)}
procedure int_str(l:longword;out s:string);
...
procedure int_str(l:longint;out s:string);
{Optimized for speed, but balanced with size.}
const digits:array[0..9] of cardinal=
(0,10,100,1000,10000,
100000,1000000,10000000,

  100000000,1000000000);

...
{$endif}

So You can try to propose your changes to "generic.inc"..

---
WBR,
Max.

FWIW, these are disabled because they cause crashes.

Jonas

I could not follow what the code does, as it is in assembly, but it looks like it has the same idea as mine.

In general, how can one propose some changes in a library? Should the suggestion goes through this mailing list?

Amir

Amir wrote

In general, how can one propose some changes in a library? Should the suggestion goes through this mailing list?

Create a patch against the FPC sources and post it as a feature to the bug tracker (http://bugs.freepascal.org ).

Jonas

Don't bother with assembler -- it's not general, just make a clean implementation of what You think, try to adopt this to "generic.inc", recompile the trunk, run test suite and then create Mantis entry with source diff. Sure it will be considered one way or another..

---
WBR,
Max.

Amir wrote

In general, how can one propose some changes in a library? Should the suggestion goes through this mailing list?

The most appropriate way seems to be to improve the existing ASM version. Of course other archs would not take advantage from this but could follow....

-Michael

That is a valid argument against improving the existing ASM code.

OTOH, for such a low-level stuff ASM _might_ provide a speed advantage.

-Michael

Michael Schnell wrote

OTOH, for such a low-level stuff ASM _might_ provide a speed advantage.

Or it means the FPC compiler has place for improvement converting Object Pascal code to ASM - generating more optimised ASM with -O2 or -O3 parameters.

G.

Op Mon, 3 Sep 2012, schreef Graeme Geldenhuys:

Certainly, but the code used in that asm implementation is quite out of reach for compilers.

Daniël

Daniël Mantione wrote on Mon, 03 Sep 2012:

Certainly, but the code used in that asm implementation is quite out of reach for compilers.

Given that we now have support for the bsr intrinsic, it should be possible to more or less literally translate it into Pascal though. The trick to change the unsigned division by a constant into a multiplication followed by a shift is also in the compiler (only for ppc and x86 currently though).

Jonas

Daniël Mantione wrote

Certainly, but the code used in that asm implementation is quite out of reach for compilers.

Certainly, but there is always scope for improvements right? eg: Delphi is well know for generating more optimised ASM than FPC. I'm by no means saying that it is easy, I'm just saying that in the long run it is easier to maintain Object Pascal code [in the case of IntToStr and similar functions], than ASM code. Not to forget the fact that such Object Pascal implementations are much more portable.

Graeme.

BTW, I found only one caveat in that asm-implementation: according to Intel docs target register of BSR is "undefined" if source=0, so Z-flag should always be checked after BSF/BSR.

In case of "int_str" ECX randomisation after BSR surely will lead to crash, but in practice I can not reproduce such spurious behavior.

---
WBR,
Max.

It will be interesting to benchmark Delphi's ARM compiler once it comes out as we had quite some work on the ARM optimizer in the last months and so there is the chance that FPC performs better on ARM than Delphi :)

Regards,
Sven

And furthermore, current intrinsic implementation of BSR/BSF also does not check Z-flag after execution. That is bad, I think.. :(

I have no AMD/etc CPU to stress-test, only Intel. So I can not guarantee the assumption of "unchanged destination, if source=0".

---
WBR,
Max.

Except that modifying the compiler to generate highly-optimised code for specific high-level tasks is probably more work than having a fragment of assembler that needs to be written once per target CPU.

Sven Barth wrote

It will be interesting to benchmark Delphi's ARM compiler once it comes out as we had quite some work on the ARM optimizer in the last months and so there is the chance that FPC performs better on ARM than Delphi :)

Well, AFAIK the Delphi compiler for ARM will be based on LLVM. So in the current state FPC will loose big time. But we're making progress, I'm benchmarking from time to time and over the last months we've gained 10-15%. But there are a lot of optimizations which are hard to solve with the current way the compiler works.

Nico

Right... I forgot that they are using LLVM -.-

Regards,
Sven

Sven Barth wrote

and so there is the chance that FPC performs better on ARM than Delphi :)

Always good to hear! :)

Graeme.

Mark Morgan Lloyd wrote

Except that modifying the compiler to generate highly-optimised code for specific high-level tasks is probably more work than having a fragment of assembler that needs to be written once per target CPU.

And writing the assembler for that one task fixes ONE problem, but still needs to be rewritten for all other target CPU's. Improving the assembler generated by FPC improves many yes I know optimisation is a difficult topic.

Regards,
- Graeme -

----- Oorspronkelijk e-mail -----

true, but... Delphi uses some hand-coded asm optimisation as well. There are "pure pascal" implementations to functions in the RTL as well as x86 and 64bit implementations.

That is for the RTL. As for the compiler itself, I've heard it was written in C(++), so usually a better fit to asm. :-)

Let's not forget by the way that a lot of much-used functionality was rewritten in asm in the fastcode project, later included by CodeGear and Delphi-compiled programs went faster from those versions on (methinks Delphi 2007).

On the other hand, the hand-optimised ASM code may have been fast(est) in that era, but with each new processor, other ways/opcodes/sequences may be faster. Anybody remember introduction of U/V pipes, L1 cache optimisation of data-access or even code-access (jmps etc), general stalling when using registers for O then I within x instructions... ? A compiler can choose to optimise those type of things in a more generic way, whereas when you have it in ASM, it is set in stone: that way and no compiler-optimisation. Either way, both have their uses and use cases. I've even seen implementations of much used functionality where on startup (x86 and Delphi), a cpuid query is done and according to certain compatibilities a set of functionality is "registered". Then they used wrapper inline functions that used the underlying record-of-function-pointers. All they needed to do then is optimise for certain combinations of cpuid flags and architectures to make it "as fast as it gets" on every PC of that architecture.

Needless to say it was not as maintainable as pascal versions, but they did get a speed-increase (even over Delphi compiler) on the time-critical and heavily used functionality, even with the indirect call in place.

kind regards,
Dimitri Smits

----- Oorspronkelijk e-mail -----

granted, it could be useful and speedup other code on the go as well, but like you said: optimisation is a difficult problem. There is not always a one-size-fits-all, and it usually is a compromise leaning towards generability of applicability or pure speed.

kind regards,
Dimitri Smits

where the compiler was able to recognise e.g. IntToStr() and apply knowledge of typical usage in its optimisations. You might remember that things like the Sieve of Eratosthenes went out of vogue as benchmarks specifically because compilers were recognising the code and "cheating".