Sure, but in a very different manner.
Look at the code yourself if you do not believe me ;-)

Sure, see attachment.
Note that I made shortstring->ansistring text replacament followed by minimal fixed to get working Add and Find methods. Other methods may be broken as a result.

I know it quite well.
But both classes serve approximately the same functional purpose: a hash.

At the moment, it's just for benchmarking.

Thank you for the code.

Michael.

Memory efficiency is a tricky notion.
True, shortstring TFPHashList stores the keys very efficiently, but the ansistring variant may probably
avoid storing them at all due to refcounting.
So, TFPHashList may plausibly end up both taking more memory (due to key duplication) _and_ more time (due to key copying).

Ok, I re-tested with 2*10^6 Find's. Then AnsiString variants wins even for length 5:

ShortString: 0.547 s
AnsiString: 0.437 s

Also Add is probably broken. I cannot see where AddStr does proper ref. counting.

Florian Klaempfl wrote

Am 20.10.2010 09:23, schrieb Alexander Klenin: Also Add is probably broken. I cannot see where AddStr does proper ref. counting.

Indeed. And after I fixed it, the Add have really slowed down by 5-50% depending on string length.
OTOH, with ansistrings the whole concept of FStrs/StrIndex is redundant, and some minor speedup may be achieved by removing it.

Can you post the fixed code ? (with optimizations or without, does not matter)

Michael.

Keep also in mind that the extra indirection of ansistrings increases cache polution (one access touches two instead of one cache line) and this might not be modelled by the test. So in a real world example shortstrings have another advantage over ansistrings. Of course, I suspect that using ansistrings against shortstrings would be hardly measurable in the compiler speed, but one hundred of such micro optimizations might make the compiler twice as fast.

Michael Van Canneyt wrote

Can you post the fixed code ? (with optimizations or without, does not matter)

Attached. The fix is rather clumsy though.
I vaguely remember that Delphi (or was it some library we used...) had something like IncRefCount procedure specifically for such cases, but I was unable to find FPC analog (except fpc_AnsiStr_Incr_Ref which is not directly callable).

All true. However, my main point was that all those micro-optimizations obfuscate the code.
One day all this obfuscation may prevent some higher-level optimization, like multi-threading or built-in linking,
which would gain more then 2x speedup.
Another point: I have actually complained about pchars, not shortstrings. Shortstrings are not any worse than AnsiStrings in usage, until one stays within 255 chars limit.
PChars, on the other hand, require manual memory management which is the source of bugs.

In our previous episode, Alexander Klenin said:

Major work like that is already always combined with major refactoring and rewriting, so that is unlikely, and they touch totally different systems (frontend vs backend)

PChars, on the other hand, require manual memory management which is the source of bugs.

Point out the example of bugs. (ones that matter, not the stylistic ones)

I am not sure I understood you point.
Is not your whole argument that the refactoring is bad/not needed?

> PChars, on the other hand, require manual memory management > which is the source of bugs. Point out the example of bugs. (ones that matter, not the stylistic ones)

This sub-thread was started by mentioning the series of errors my student made when trying to implement case of string. Most of them was due to the fact the code used pchars and records instead of strings and (hierarchy of) objects.
Surely, a more qualified developer would probably have avoided these, but still I think this is a good demonstration of adverse side-effects of micro-optimizations.

In our previous episode, Alexander Klenin said:

No, first mine is conditional on "as needed" (and I also wrote in the message that the chance is low since they are different subsystems),

while yours was up front and unconditional.

Second, it might not be the same refactoring, since the "as needed" refactoring might need to adress additional points that come up in the implementation/design of the feature that actually needs the refactor.

Note that I'm purely reacting to your reasoning, and it has nothing to do with my opinion on the shortstring/ansistring matter. (in which I might be described as being in the ansistring camp, mainly because of the 255 limit and the fact that I'm told that that is a reason to not have unit qualifications in parameter mangling).

Yes. But that might be a result that FPC is oriented towards production, and not towards education.

Surely, a more qualified developer would probably have avoided these, but still I think this is a good demonstration of adverse side-effects of micro-optimizations.

It is why this is frowned on in educational oriented projects. But FPC is not oriented oriented, its mission goal is being an usable, production compiler. And speedy use is a main factor, and goes above quick entry of students.

FPC is a production compiler and not an educational project. See Martin's email, people care about the speed of FPC.

Surely I did not imply that lowering barrier for entry should be the primary goal of the FPC project (although that would be a nice side-effect). I meant to demonstrate that the current code structure encourages failure, which, of course, may be overcome with enough effort by highly-qualified developer.

Imo somebody working on a compiler should understand pchars and use them properly as well as e.g. a compiler developer needs very good assembler knowledge.

Alexander Klenin пишет:

Running the test, I get quite opposite results:

0.750 sec
0.766 sec
short add: 1.829 sec
short find: 0.781 sec
ansi add: 1.750 sec
ansi find: 1.406 sec

The only modifications I made to the test is added printing separate numbers for 'find' and 'add', and printing labels. Modified test is attached.

Although theoretically Find() should show no difference at all, because it performs the same operations on the same data. IOW, the difference seen is caused either by CPU cache effects, or by bugs in testing.

No difference between the first two numbers (IntToStr for ShortString and AnsiString) is also quite suspicious...

Regards,
Sergei

What CPU? I have Core i3 540.

Although theoretically Find() should show no difference at all, because it performs the same operations on the same data. IOW, the difference seen is caused either by CPU cache effects, or by bugs in testing.

I suspect that the main culprit may be the relatively slow implementation of built-in AnsiString operator=.
ShortString code contains a strange construct in InternalFind function, clearly designed to bypass built-in operator=.
I removed that construct during ansistring conversion.

No difference between the first two numbers (IntToStr for ShortString and AnsiString) is also quite suspicious...

This is probably because the time is dominated by the conversion itself. IOW, IntToStr is so slow that string type does not matter in comparison.

Alexander Klenin пишет:

Mine is Core2Duo E7200.

Ah, that's an artifact from old days. It was removed a while ago from compiler's cclasses.pas, but nobody took care to promote those changes to contnrs.pas. Probably I should do that.

The conversion itself is just "divide by 10, add ord('0')" per digit. Should be that way, at least. It is a point to have a closer look at (for me :).

Regards,
Sergei

> PChars, on the other hand, require manual memory management > which is the source of bugs. Point out the example of bugs. (ones that matter, not the stylistic ones)

The usage of PString essentially is using an crippled AnsiString, without reference counting. I did not yet find any (obvious) bugs, but several flaws where ShortStrings are allocated, copied and disposed for no reason. See pmodules.try_consume_hintdirective.

DoDi

Hans-Peter Diettrich пишет:

In pmodules.try_consume_hintdirective, copying happens exactly once; if you write something like "type foo=class end deprecated 'a' deprecated 'b';" it will end up with IE200910181. That deserves a fix with a more user-friendly error message, but the logic is correct.

Regards,
Sergei

I've done some some optimizations of tFPHashList and results are (for 10^6 calls average length 30 characters):
from svn: 2.234s
uhla : 2.297
my : 2.044

that is 10% shorter (or even better, because string generation consume about 1.4s)
full source in attachment (should I prepare it different?)

changes are made in: FPHash and some minor in StrExpand,AddStr, Add

Second: when I review assembler list I've notice some strange lines (all optimizations are enabled):

# [124] dec(ii);
movl %esi,%eax
decl %eax
movl %eax,%esi
.Lj16:
movl %esi,%eax <- this is not necessary
testl %eax,%eax
jg .Lj15

In source this is
while ii>0 do begin
..
dec(ii)
end;

Can be added some optimizations to avoid this doubled move.

Dariusz Mazur wrote

full source in attachment (should I prepare it different?)

The best would be a diff against compiler sources.

Which compiler version? 2.4.x? I think r15502 in trunk should fix this.

I don't see where .Lj16 is jumped to from, but this indeed looks rather strange.

decl %esi
jg .Lj15

seems to have the same effect at the first glance. But maybe I have the jump conditions wrong, the test instruction always clears the overflow flag.

Vinzent.

W dniu 2010-10-22 23:30, Florian Klämpfl pisze:

Am 22.10.2010 23:17, schrieb Dariusz Mazur: > full source in attachment (should I prepare it different?) The best would be a diff against compiler sources.

OK. First I find better computing of hash. My is slight worse than current (but overall faster)

> Second: when I review assembler list I've notice some strange lines (all > optimizations are enabled): > Which compiler version? 2.4.x? I think r15502 in trunk should fix this.

2.5.1 but older. Now I test from current. Its better (faster) but I found other strange:

first: dec(i) is translate to three lines
movl %esi,%eax
decl %eax
movl %eax,%esi

why not simple decl %esi ?
When variable is in %ebx things are the same.

second  if I have:
   while ii>0 do begin
      ....;
    dec(ii);

assembler look:

# [121] while ii>0 do begin
jmp .Lj16 //< here add first test of ii
.balign 4,0x90
.Lj15:
.Ll8:
# [122] result:=LongWord(result *8010817 ) xor (Pw^); .Ll10:
# [124] dec(ii);
movl %esi,%eax
decl %eax
movl %eax,%esi
.Lj16:
testl %esi,%esi //<-- this can be avoid, because test from DECL jg .Lj15

Is this possible to achieve this optimizations,
If yes, can somebody help, from which file I should start

Yes. I saw this too and I didn't find the cause, especially because I were not able to reproduce it in a small example.

Replacing the jmp by a test and jz is two-fold: it increases code size (thus higher code cache pollution) and it pollutes the branch prediction unit while an uncoditional jump is very cheap on modern processers.

W dniu 2010-10-23 23:04, Florian Klämpfl pisze:

attached before uhlm.pas is too long? its form fpHash

You don't understand me
My proposition is moving one instruction, outside loop

# [121] while ii>0 do begin
testl %esi,%esi //<-- this should be added, because after .Lj16 test is absent jmp .Lj16 // jmp not change ZF
.balign 4,0x90
.Lj15:
.Ll8:
# [122] result:=LongWord(result *8010817 ) xor (Pw^); .Ll10:
# [124] dec(ii);
decl %esi
.Lj16:
jg .Lj15 // ZF is setting by decl (first timie by testl)