Forum > FPC development
Why loaded units are TLinkedList and not LinkedDictionary
daniel_sap:
--- Quote from: 440bx on March 15, 2021, 08:42:40 am ---
--- Quote from: daniel_sap on March 15, 2021, 07:57:27 am ---If there are 1000 units in project it will do 1000*500 unnecesary iterations. But if you have more this grows exponentially.
--- End quote ---
Since I haven't looked in detail at the entire mechanism FPC uses to keep track of units, I could be wrong about what follows but, units are scoped, therefore the number of units the compiler has to keep track of for either another unit or the program itself should normally be small. That is often _not_ a large number of units and, in many cases, it should be a small number, usually 10 or less (unit names in scope, that is, listed in the unit's "uses" clause.) Because of that, it really doesn't make much sense to use an elaborate structure to keep track of them, IOW, the total time spent adding and searching the units in a linear structure will often be as fast or faster than the total time used by a more sophisticated structure/algorithm.
Now, if one unit or program _directly_ uses 1000 units, (that is they are all in the same scope), then yes, the search is going to be slow but, if I saw a unit or program listing 1000 units in its "uses" clauses, I wouldn't even bother to read the code.
HTH.
--- End quote ---
There are a few units with around 100 uses. Most of the units are very compact with just a few units in the uses clause.
However, in the loaded_units list i have thousands of loaded units, which makes me think that this could be improved.
I didn't check how much time exactly is lost in this iterations, just see they are a lot.
I started the debugging of the code cause in Delphi the same program compiles for a minute or so, and here the compilation takes like 7 times more.
I try with quick compile, but sometimes I face issues with that. May be because I use the code of the trunk.
However, I will be happy to save more time on compilation and that's why I started to dig deeper in the compiler code and make notices about the potential issues.
As I am new to the code, it is possible to make wrong assumptions, that's why I write here in the forum.
To visualize better the issue I attached a screen shot. There I put a breakpoint in the addloadedunit procedure with hitcount 200 in the breakpoint properties.
--- Quote from: Jonas Maebe on March 15, 2021, 11:31:20 am ---I profile the compiler occasionally. There are seldom specific places where a lot of time is spent. It obviously also depends on the source code you are compiling. Compiling the MacOSAll unit (which contains almost only declarations and barely any code) gives a quite different result than compiling the compiler itself. Most performance gains until now were actually by adding prefetch intrinsics in places where we walk over large linked lists (but that only helps if the loop does a lot of work, so the prefetch has time to complete before the next element is fetched).
--- End quote ---
I was wandering if I can profile the compilation also. May be you use some tool and give me some advice how can I proceed with that.
--- Quote from: marcov on March 15, 2021, 09:23:29 am ---1. TDictionary is new since last 3.2.0 last may
2. Compiler can only use RTL, not packages.
That is not a whole excuse, quite often scaled down container types are brought into the compiler when there is need.
IOW usually historic reasons.
--- End quote ---
Good to know.
I suppose that the TDictionary will be fast for searching but slow for adding and removing.
However, I was thinking about something like LinkedHashMap which will make the adding and removing very fast, also the searching very fast.
I see implementation of Dictionary in cclasses.pas which looks a little specific for concrete purpose. Looks like it locates symbols by name - TFPHashList.
I will check this TFPHashMap thoroughly, may be this could be a good foundation for LinkedHashMap.
As far as I know some kind of equivalent of LinkedHashMap in Delphi is TStringList. Need to check if it is fast enough on adding and removing single items. May be with beginUpdate is fast but for single item could be slower.
I'm planing to change the
loaded_units : tlinkedlist; { All loaded units }
to
loaded_units : TLinkedHasMap; { All loaded units }
However, I'm not deep in the code and don't feel so sure in my assumptions. That's one of the reasons I asked here if someone knows better and explain the reason why TLinkedList is used.
And also if someone knows some good LinkedHashMap equivalent for FPC
Jonas Maebe:
--- Quote ---I was wandering if I can profile the compilation also. May be you use some tool and give me some advice how can I proceed with that.
--- End quote ---
I do this under macOS. I compile the compiler with debug information and then run it with the "instruments" tool with the "Time Profile" template. That temlpate samples the process every 1ms and generates a profile based on that.
ASBzone:
--- Quote from: Jonas Maebe on March 15, 2021, 09:48:32 pm ---
--- Quote ---I was wandering if I can profile the compilation also. May be you use some tool and give me some advice how can I proceed with that.
--- End quote ---
I do this under macOS. I compile the compiler with debug information and then run it with the "instruments" tool with the "Time Profile" template. That temlpate samples the process every 1ms and generates a profile based on that.
--- End quote ---
@Jonas, is there any value to profiling the compiler on multiple OSes/platforms?
Jonas Maebe:
--- Quote from: ASBzone on March 15, 2021, 09:56:32 pm ---
--- Quote from: Jonas Maebe on March 15, 2021, 09:48:32 pm ---
--- Quote ---I was wandering if I can profile the compilation also. May be you use some tool and give me some advice how can I proceed with that.
--- End quote ---
I do this under macOS. I compile the compiler with debug information and then run it with the "instruments" tool with the "Time Profile" template. That temlpate samples the process every 1ms and generates a profile based on that.
--- End quote ---
@Jonas, is there any value to profiling the compiler on multiple OSes/platforms?
--- End quote ---
There is some value in doing it on multiple architectures. Doing it on different OSes won't generally show much difference.
ASBzone:
--- Quote from: Jonas Maebe on March 15, 2021, 10:02:18 pm ---
--- Quote from: ASBzone on March 15, 2021, 09:56:32 pm ---@Jonas, is there any value to profiling the compiler on multiple OSes/platforms?
--- End quote ---
There is some value in doing it on multiple architectures. Doing it on different OSes won't generally show much difference.
--- End quote ---
Thanks, @Jonas
Navigation
[0] Message Index
[#] Next page
[*] Previous page