Forum > FPC development
Why loaded units are TLinkedList and not LinkedDictionary
daniel_sap:
Hi,
I am porting Delphi app to Lazarus and see that it takes a little longer to compile compared to Delphi.
I opened the ppcx64 project from compiler directory and start debugging the compiling of my project.
One thing I noticed is that all units that are loaded are kept in
loaded_units: TLinkedList (in fmodule.pas)
Procedure addloadedunit (in fmodule.pas) is used to add a unit to loaded_units. Called by registerunit (in fppu.pas)
It is fast to add item in linked list. No reallocation and move of memory.
There are some methods that iterates through loaded_units linked list
resolve_unit (in fmodule.pas)
registerunit (in fppu.pas)
This registerunit function is called every time a unit is read/loaded (readloadunit in fppu.pas)
and it iterates through all linked list items of loaded_units.
In many cases this iterates through all items without finding anything (every time a new unit is loaded)
If there are 1000 units in project it will do 1000*500 unnecesary iterations. But if you have more this grows exponentially.
Generally registerunit is called when a unit is in uses clause of compiling unit. This means that it will do these iterations not only when unit is loaded for first time.
It is called every time the unit is used. Which makes the number of iterations even more. In this case it will not iterate through all but still.
Cause registerunit is searching for module object by given unit name for me it looks natural to use Dictionary.
Why to make so many unnecessary iterations.
However, I suppose that Linked list is preferred for faster add and remove from loaded_units avoiding the memory reallocation;
In java I typically use LinkedHashMap class which combines both of the strengths of LinkedList and Dictionary.
My question is, cause I don't have much experience with compiler code.
Am I thinking right? Is there something that I'm missing.
Can this functionality be improved? How can this happen?
Is there such thing like LinkedHashMap in free pascal?
Regards and thank you
440bx:
--- 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.
marcov:
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.
JuhaManninen:
--- Quote from: marcov on March 15, 2021, 09:23:29 am ---That is not a whole excuse, quite often scaled down container types are brought into the compiler when there is need.
--- End quote ---
This interests me because I optimized Lazarus IDE code recently.
I wrote in Laz mailing list about the tools "Profiling with Valgrind and KCacheGrind".
It makes a nice pair of tools.
How much are people profiling FPC? I may do it at some point. The results of profiling often surprise. The solutions to optimize are not always obvious though.
Jonas Maebe:
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).
Navigation
[0] Message Index
[#] Next page