Hello,

Does FPC capable of supporting
blackfin<http://www.analog.com/en/embedded-processing-dsp/processors/index.html>(and others in it's family) CPU ?
It seems that more and more embedded projects starting to use it.

Ido
http://ik.homelinux.org/

No.

In fact I did a (quite low priority) research on how to port FPC to a new CPU such as NIOS and Blackfin and found that it of course is doable somehow. While NIOS seems to look more doable, as it's quite similar to MIPS (and ARM), Blackfin has a much more complex instruction set with a huge potential for low-level optimization. Thus I suppose Blackfin is quite hard to do.

OTOH I have the impression that the real winner with embedded projects will be ARM (especially Cortex) and here Linux is getting interesting for even lower-size and higher-Volume projects. So I am shifting my interests towards Linux enabled embedded ARM chips (like the TI AM1x and AM3x "Sitara" series that has been introduced in 2010 and feature a RISK coprocessor for hard realtime / virtual peripheral stuff).

-Michael

Hi Michael

I too am planning to switch to 'sitara' AM3517 SBCs from at91sam9263. Hope there would be an effort to an fpc port to this board on linux-uclibc.

regards

Nataraj

I understand that the Cortex A8 which powers the AM3x features the full 32 bit "ARM" instruction set plus the 16 Bit "Thumb" instruction set plus several enhancements. Thus code created by FPC/ARM should just run out of the box.

In the Lazarus mailing list, we lately discussed how to special do stuff like "atomic instructions" and "Futex without libc binding". Here ARM-Linux offers a shared userland page with functions that are always provided in a version optimized for the CPU subarch we are running on. Using same in the RTL instead of doing our own (non sub-arch optimized at runtime) code would be a nice enhancement for the RTL

-Michael

I would be interested in knowing whether it would be feasible to create DSP backends for FPC. I recently had the experience of using a TMS320C26 which probably has to be programmed in assembler due to the limits of the instruction set. But I hear newer DSPs use instruction sets geared alot more towards highlevel compilers

Michael:
Cortex A8 runs ARMv7A. All the Interlocked* functions in the ARM RTL already have implementations for >ARMv6 instructions(ldrex/strex) which is pretty much what the architecture manual wrote as example code

Jeppe Johansen wrote

Cortex A8 runs ARMv7A. All the Interlocked* functions in the ARM RTL already have implementations for ARMv6 instructions(ldrex/strex) which is pretty much what the architecture manual wrote as example code

I do know this. But as at compile time the compiler (person) can't know on what sub-arch the user (person) will run the program he can't tell the compiler (program) for which sub-arch to create the binary. So he likely will use the default setting which is ARMv5 and does not use the "modern" atomic-supporting instructions.

That is why the Linux Kernel community provides us with this common page providing "interlocked" ("atomic" in Linux-language) userland Functions automatically optimized appropriately. It would be a real shame not to take advantage of this in a Linux environment. I feel using these function is really easy and will not even need ASM (just calling a function at a fixed address).

-Michael

BTW.:
The v5 workaround code not only is less efficient (doing busy splinocks), it also creates potential deadlocks in certain cases (realtime priority), is not 100% secure and it might be that certain chips even fail handling the swap instruction atomicly and thus the code will not , IMHO, basing the userland part of Futex on this is not recommended.

The "common" Linux functions are guaranteed to work decently (with Kernel support if necessary) and always are as fast as possible.

-Michael

I would be interested in knowing whether it would be feasible to create DSP backends for FPC.

As usual: a matter of time.

Yes, but the code is not selected dynamically: if one compiles for armv5 but runs it on a armv6+, the armv6 doesn't use the new instructions.

Maybe you should write a patch before you have to repeat this for the next ten years.

Florian Klaempfl wrote

Maybe you should write a patch before you have to repeat this for the next ten years.

As already said in the other thread I'll do this as soon as I will have the appropriate equipment to test it. Until that point of time I only can do research and hope for others to do the implementation. If anybody thinks I can be of any further help please let me know.

-Michael

True, but do you think anyone does that? :) Most people know what end hardware their programs will run on

I don't think we can have support for both in the rtl. I don't even think you can do that, since GNU as won't accept ARMv6 instructions if you assemble for ARMv5, and throw an error

Well, you can always assemble for ARMv6 but use only ARMv5 instructions when running on ARMv5. This is what the rtl does with the PLD instruction in system.move: a system.move procedure with PLD is only used when the CPU supports it.

Of course, this aims more towards generic arm-linux programs than embedded stuff where you usually build your custom rtl anyways.

Jeppe Johansen wrote

True, but do you think anyone does that? :) Most people know what end hardware their programs will run on

in fact to work decently, the v5 version needs Kernel support (if an interrupt is issued while doing the atomic stuff) that only is possible by using the Linux provided functions (only available if you really compile for Linux, of course).

The v6+ code is a pure userland thingy and thus the RTL implementation is fine.

-Michael

Florian Klaempfl wrote on Fri, 09 Jul 2010:

At least if you use the VFP, you have to compile all code for the correct cpu, because the compiler has to use different versions of the "load/store multiple vfp registers" instructions for pre-ARMv6 and for ARMv6 and later in the function prologs.

Jonas

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

Let me know if you (or somebody else) has more concrete plans on the integration of a new CPU. I just stripped down the machine files for a no_cpu machine (all fakes), with some documentation about the required units etc. An implementation of a new CPU, based on that skeleton, would rise the priority for further explorations and documentation.

I already have more suggestions for easier implementation of new machines...

DoDi

This IMO would require new language elements, for parallel/vector operations, dedicated libraries, or *very* clever optimizers. A general-purpose language like Pascal is not suited for coding DSP operations.

DoDi

FPC has already basic MMX support by allowing operations on appropriate arrays so DSP support could be added based on such approach or just using intrinsics.

Hans-Peter Diettrich wrote

Let me know if you (or somebody else) has more concrete plans on the integration of a new CPU.

I remember some discussions about doing a MIPS / PIC32 port recently

I just stripped down the machine files for a no_cpu machine (all fakes), with some documentation about the required units etc.

Is this based on what we already have for X86, ARM, etc, or does it "fork" to another set of ARC implementations ? If "fork", is it intended / viable to move the existing implementations into that scheme ?

An implementation of a new CPU, based on that skeleton, would rise the priority for further explorations and documentation.

No idea in what state the structure / documentation of the existing fully supported implementations such as x86 and ARM is.

-Michael

The no_cpu skeleton was stripped down from the M68K machine, which in turn seems to have inherited from the ARM. Due to hard coded dependencies it was impossible to remove e.g. registers completely, and also a $define of some already known machine must be given, else every compilation will fail immediately with an $fatal error.

That skeleton reflects the units, data structures and procedures, that are referenced by other parts of the compiler (hard coded). Every machine consists of a formal description (registers, instructions...), node generators for the parse tree, code (tree) optimizers, assembler and output generators for binary code and debug info. A distinct machine back-end is selected by adding its source folder to the unit search path. This may be the fastest possible implementation for one (of multiple) machines, but it doesn't allow to support multiple machine back-ends in one program. The same applies to the front-ends, which currently are not flexibility would require a
plug-in scheme or similar, hard to do without dynamically loadable packages. But since some abstract links already exist (class type variables for machine specific descendants), these links could be exchanged at runtime, not only in the initialization section of the machine specific units. Then it would be sufficient to add all (wanted) front- or back-ends to the compiler, and switch amongst these at runtime. Where switching the target machine at runtime does not make much sense to me, in contrast to switching front-ends based on the source file types.

I could not find much, and most existing documentation is outdated since 2.0 :-(

Some parts, like the parse tree nodes, are somewhat self-explaining. The formal machine descriptions (registers, options...) are almost undocumented. I tried to make the construction of the register descriptor constants more transparent, by composing them from other sets of constants. There seem to exist tools that produce e.g. register descriptors (in include files), but I did not yet dig into the tools folder.

DoDi

But since some abstract links already exist (class type variables for machine specific descendants), these links could be exchanged at runtime,

One problem are all the used constants describing the target architecture. We discussed multiple back-ends in one compiler already in 2002 and saw no advantage in it so we didn't try to solve it and we decided to use the fpc -P ... solution which makes no difference for the user.

For me, a much higher priority when doing rewrites might be multithreading nf the compiler itself.

Full ACK.

For me, a much higher priority when doing rewrites might be multithreading nf the compiler itself.

That's questionable, depending on the real bottlenecks in compiler operation. I suspect that disk I/O is the narrowest bottleneck, that can not be widened by parallel processing. It also requires further research, for e.g. the determination of the optimal number of threads, depending on the currently available resources on a concrete machine.

But of course it's worth a try, to find out more...

DoDi

Unless you are doing a cold compile, the main bottlenecks in the compiler are the memory manager (mostly the allocation of memory, freeing is faster), zero-filling new class instances (and partially resetting the register allocator) and tobject.initinstance.

It also requires further research, for e.g. the determination of the optimal number of threads, depending on the currently available resources on a concrete machine.

We'd just use the same approach as make: allow the user to specify the number of parallel operations.

Jonas

Hans-Peter Diettrich wrote

That's questionable, depending on the real bottlenecks in compiler operation. I suspect that disk I/O is the narrowest bottleneck,

I doubt this. The disk-cache does a decent work here. gcc can do this very effectively on a higher layer, as for each source file gcc is called separately by make. As FPC internally organizes the unit "make" sequence, I suppose internal multithreading needs to be implemented.

-Michael

Hans-Peter Diettrich wrote

M68K machine, which in turn seems to have inherited from the ARM.

I suppose: vice versa :).

.., but it doesn't allow to support multiple machine back-ends in one program.

Do you think it would be an advantage to support multiple archs in a single compiler executable ? I feel that recompiling the compiler when changing the target CPU is not very harmful.

I could not find much, and most existing documentation is outdated since 2.0 :-(

Of course improvement on that issue would be very desirable :).

-Michael

Memory throughput is a bottleneck, I/O not really. So multithreading has a real advantage on NUMA systems and systems where different cores have dedicated caches. One or two years ago, I did some experiments with asynchronous assembler calls and it already improved significantly compilation times on platforms using an external assembler. The problem is that the whole compiler is not designed to do so. This could be solved by an approach we want to implement for years: split the compilation process into tasks (like parse unit X, load unit Y, code gen unit X) with dependencies. This should also solve the fundamental problems with unit loading/compilation causing sometimes internal errors. The first step would be to do this without multithreading, later it could be tried to execute several tasks in parallel.

In our previous episode, Hans-Peter Diettrich said:

No that has to be solved by a bigger granularity (compiling more units in one go). That avoids ppu reloading and limits directory searching (there is a cache iirc) freeing up more bandwidth for source loading.

Not only compiling goes in paralel, I assume one could also load a ppu in parallel? (and so parallelize the blocking time of the disk I/O and the parsing of the .ppu contents.

With compiling I meant all tasks the compiler does, even assemling and linking.

Memory management can not normally be parallelized. Also access to the newly created instances requires to fill the cache, so that IMO fear that parallel operations in this area will not speed up anything much. But since more is done in a thread, there may remain tasks that can fill the gaps in other threads.

Did you already do some performance analysis in the compiler code? I never did so myself, and don't know how to obtain really meaningful figures.

A safe bet :-)

DoDi

A C compiler has to access the very same header files over and over again, so that a file cache can reduce disk I/O considerably. But when FPC processes every source unit in a project only once, the file cache is not very helpful.

Nontheless it may make sense to process the units in threads, so that an already read unit can be processed while other threads still are waiting for disk I/O. I only doubt that this will result in a noticeable overall speed gain, when the results have to be written back to disk after compilation. But we can know more only after according tests...

DoDi

Hans-Peter Diettrich wrote

Memory management can not normally be parallelized.

The FPC memory manager even can handle handle threaded access to the memory manager without OS help using atomic instructions (if running on X86 or ARMv6)

-Michael

Hans-Peter Diettrich wrote

But when FPC processes every source unit in a project only once, the file cache is not very helpful.

Obviously, a sufficiently huge cache can avoid any disk I/O bottleneck when doing the 2nd+ build.

-Michael

> M68K machine, which in turn seems to have inherited from the ARM. I suppose: vice versa :).

At least I found files with comments from/for ARM.

I don't understand the current compilation process yet. How is the target command line switch handled? Does pp spawn the target-specific compiler?

> I could not find much, and most existing documentation is outdated > since 2.0 :-( Of course improvement on that issue would be very desirable :).

What format should it be? Wiki entries were easily extensible, but it's also easy to loose the overview over the missing pieces. FPDoc is nasty to format, though it would allow to inline the documentation with the online help. I'd prefer HTML, or OpenOffice if it allows for embedded links.

DoDi

Good to know :-)

I should know more about available threading features (blocking, synchronization...). IMO compilation should be done in two steps, with the first step providing the interface for used units, from a .ppu file or by a new parse. Once this information is available, the using units (threads) can resume their work. The final code generation can occur in further threads.

At least I know now what to look for, in my parser redesign. It seems to be a good idea to reduce the number of global links, so that in a following compiler redesign multiple threads can do their work independently.

DoDi

ACK. The compiler should process in one go as many units as possible - but this is more a matter of the framework (Make, Lazarus...), that should pass complete lists of units to the compiler (projects, packages).

As a workaround a dedicated server process could hold the least recently processed unit objects in RAM, for use in immediately following compilation of other units. But this would only cure the symptoms, not the reason for slow compiles :-(

Not only compiling goes in paralel, I assume one could also load a ppu in parallel? (and so parallelize the blocking time of the disk I/O and the parsing of the .ppu contents.

It may be a good idea to implement different models, that either read entire files or use the current (buffered) access. Depending on disk fragmentation it may be faster to read entire (unfragmented) source or ppu files, before requests for other files can cause disk seeks and slow down continued reading of files from other places. Both models can be used concurrently, when an arbitration is possible from certain system (load) parameters. In the easy case an adjustable source file buffer size (command line argument) would allow to check and optimize file processing from outside the compiler, independently from (future) internal threading.

DoDi

In our previous episode, Hans-Peter Diettrich said:

Not necessarily. One could also strengthen the make capabilities of the compiler, think about reworking the compiler to be kept resident etc.

As a workaround a dedicated server process could hold the least recently processed unit objects in RAM, for use in immediately following compilation of other units. But this would only cure the symptoms, not the reason for slow compiles :-(

(some random wild thinking:)

Jonas seems to indicate most is due to the object model (zeroing) and memorymanagement in general.

One must keep in mind though that he probably measures on a *nix, and there is a reason why on Windows the make cycle takes twice the time on Windows. I don't think under Windows, the CPU or the cache halves in speed, so it must be more in the I/O sphere:
- ntfs is relatively slow in directory operations (seeking)
- Windows is slow starting up binaries.
- Afaik ntfs caching is optimized for fileserver use, not to speed up a single application strongly. Specially if that apps starts/stops constantly (a model that is foreign on Windows)

So one can't entirely rule out limiting I/O and number of compiler startups, since not all OSes are alike.

For the memory management issues, an memory manager specifically for the compiler is the solution first hand. To make it worthwhile to have a list of zeroed blocks (and have a thread zero big blocks), somehow the system must know when a zeroed block is needed. For objects this maybe could be by creating a new root object, and deriving every object from it (cclasses etc). But that would still leave dynamic arrays and manually allocated memory.

For manually allocated memory of always the same size (virtual register map?) a pooling solution could be found.

Most OSes already read several 10s of kbs in advance. I don't really think that will bring that much. Such approaches are so lowlevel that the OS could do it, and probably it will.

Then the system file cache will make it hard to determine reasonable figures for the first build. And I wonder how often long builds are run more often in sequence?

When we rely on an OS file chache, we can read all files entirely into memory, instead of using buffered I/O. Or we can design an interface that allows to run the compiler e.g. inside Lazarus, using the already loaded editor files and directory caches.

BTW, should we switch the thread topic?

DoDi

One must keep in mind though that he probably measures on a *nix, and there is a reason why on Windows the make cycle takes twice the time on Windows.

One of these issues are memory mapped files, that can speed up file access a lot (I've been told), perhaps because it maps directly to the system file cache?

So one can't entirely rule out limiting I/O and number of compiler startups, since not all OSes are alike.

That means optimizing for one platform may slow down the compiler on other platforms :-(

When zeroing blocks really is an issue, then I suspect that it's more an issue of memory chaches. This would mean that the data locality should be increased, i.e. related pieces of data should reside physically next each other (same page). Most list implementations (TList) tend to spread the list and its entries across the address space.

Special considerations may apply to 64 bit systems, with an (currently) almost unlimited address space. There it might be a good idea to allocate lists bigger than really needed, what should do no harm when the unused elements never are allocated to RAM (thanks to paged memory management). Then a TList with buckets only is slower on such a system, for no other gain.

For manually allocated memory of always the same size (virtual register map?) a pooling solution could be found.

Again candidates for huge pre-allocated memory arrays. But when these elements then are not used together, they may occupy one or two memory pages, and the remaining RAM in these pages is unused.

Most OSes already read several 10s of kbs in advance. I don't really think that will bring that much. Such approaches are so lowlevel that the OS could do it, and probably it will.

Every OS with MMF will do so, when memory mapped files only are used. The rest IMO is so platform specific, that a single optimization strategy may not be a good solution for other platforms.

But I think that such low-level considerations should be left for later, when the big issues are fixed, and the requirements for exploring the real behaviour of various strategies have been implemented.

DoDi

In our previous episode, Hans-Peter Diettrich said:

As said, I always had the feeling that it was binary startup time, and directory I/O rather than basic blockwrite/read speed.

Most files are tens of kbs max, and will probably be read entirely anyway by the system.

Hans-Peter Diettrich wrote

When we rely on an OS file chache, we can read all files entirely into memory, instead of using buffered I/O.

Loading the complete file instead of parts of it would do unnecessary memory copies.

In fact I suppose using file mapping instead of read (and maybe write) should improve speed in many cases.

-Michael

Hans-Peter Diettrich wrote

It may be a good idea to implement different models, that either read entire files...

"read" -> "map"
-Michael

Hans-Peter Diettrich wrote

One of these issues are memory mapped files, that can speed up file access a lot (I've been told), perhaps because it maps directly to the system file cache?

AFAIK File Mapping is used a lot and very successfully with Linux, but it _is_ available with NTFS. No idea if, here, the implementation is done in a way this it's really fast.

-Michael

In our previous episode, Michael Schnell said:

I've tried it long ago in win2000, and maybe even XP. If you linearly access the files with a large enough blocksize (8 or 16kb), it was hardly measurable. (+/- 300MB files).

Probably if you go linearly, the readahead is already near efficient.

But FPC might not adhere to this scheme, I don't know if FPC currently loads the whole file or leaves the file open while it processes e.g. a .inc.

If it doesn't load the whole file, opening others triggers head movement (if not in cache) that could be avoided.

Mapping does not change that picture (the head still has to move if you access a previously unread block). Mapping mainly is more about
- zero-copy access to file content
- and uses the VM system to cache _already accessed_ blocks.

The compiler does not do enough I/O to make the first worthwhile, the second is irrelevant to the compiler;s access pattern.

The only way it could matter if the memory mapped file reads more sectors speculatively after a page access, but I don't know if that is the case, it might be as well be less. (since normal File I/O is more likely to be linear)

So in summary, I think _maybe_ reading the whole file always might win a bit in filereading performance. I don't expect memory mapping to do so.

The whole file hypothesis could be easily testable (if applies at all) by increasing the buffersize. But if I understand finput.pas properly, FPC already uses a 64k buffersize (which is larger than most sourcefiles), so I don't expect much gain here.

And, worse, I think that even if that results in a gain is dwarfed by directory operations (searching files, creating new files) and binary startup time. (of compiler but also other tools).

(*) empirical time for a core2 to move a large block. (source+dest >cache)

Hans-Peter Diettrich wrote

Memory management can not normally be parallelized.

What's this then: http://topsoftwaresite.nl/ You are talking cows dung. It is actually in production at one of the largest stockbrokers in Europe. You should have written : "It is hard to do parallization"

The link is for a very good scaling memorymanager over multi processor systems provided the software is also well written. Ivo's memorymanager is even lock free, if you use it properly.

Thaddy wrote on Wed, 14 Jul 2010:

Please try not to add emotionally laden terms like that to your posts.

Thanks,

Jonas
FPC mailing lists admin

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

A fact has nothing to do with emotions. Check that code. Then write a review.

Thaddy wrote

A fact has nothing to do with emotions. Check that code. Then write a review.

I presume he was talking about the cow's dung.

How that? Of course the entire file uses more address space than a smaller buffer, but when the file is parsed, the same number of bytes must be copied to local memory in either case.

And when the entire file sits in memory, the scanner and parser operations can be optimized for much higher speed, by e.g. removing unnecessary address calculations, bounds checks and string copies.

In fact I suppose using file mapping instead of read (and maybe write) should improve speed in many cases.

Therefore my question about a platform independent solution for MMF.

At least we could implement a MMF (source) file class, that emulates this feature on platforms without MMF support. Support also could be restricted to map only entire files, for the compiler - otherwise the management of mapping windows would degrade the achievable performance.

DoDi

I've heard it the opposite way, that it has become available for *certain* Linux distros as well ;-)

And Delphi (Windows!) users reported noticeable performance boosts (factor 3+), even if nobody ever came up with non-trivial example code, including fallbacks for restricted (32 bit) address space.

DoDi

Windows offers certain file attributes for that purpose, that notify the OS of intended (strictly) sequential file reads - what would allow to read-ahead more file content into the system cache.

Mapping does not change that picture (the head still has to move if you access a previously unread block). Mapping mainly is more about - zero-copy access to file content - and uses the VM system to cache _already accessed_ blocks.

- and backs up RAM pages by the original file, they never will end up in the swap file.

The whole file hypothesis could be easily testable (if applies at all) by increasing the buffersize. But if I understand finput.pas properly, FPC already uses a 64k buffersize (which is larger than most sourcefiles), so I don't expect much gain here.

I see the biggest benefit in many possible optimization in the scanner and parser, which can be implemented *only if* an entire file resides in memory. When memory management and (string) copies really are as expensive as some people say, then these *additional* optimizations should give the really achievable speed gain.

IMO we should give these additional optimziations an try, independent from the use of MMF. When an entire source file is loaded into memory, we can measure the time between reading the first token and hitting EOF in the parser, eliminating all uncertain MMF/file cache timing.

It's only a matter of the acceptance of such a refactored model, since it's a waste of time when it never will become part of the trunk, for already known reasons.

DoDi

My point is: when multiple threads try to acquire an new memory block at the same time, and they happen to find the same gap, then only one of these can win. The other threads must continue or - in the worst case - restart their search for the next matching gap.

So IMO only a low *chance* for such concurrent tries can result in *typically* better performance of such a memory management model. With increasing memory fragmentation the collision chance increases as well.

DoDi

Just look at the FPC memory manager: to avoid this some structures like the freelist are thread specific.

In our previous episode, Hans-Peter Diettrich said:

I can vaguely remember something like that too. It is a matter of hacking that into the RTL, and then measure make cycle (requires a few reboots to preclude caching)

If swapping enters the picture, then all these savings are peanuts, so we assume that is absent.

That's easily said, but often when you enter the details, you have to often make compromises. And sacrifice speed.

I don't think we ever going to give an up front carte blanche for a massive rewrite to go into trunk. That is simply not sane.

A subsmission will always be judged on performance and maintainability before being admitted.

If this bothers you, try to find smart ways to phase the changes, and limit yourself to a few things at a time, and don't try to speedoptimize I/O, change parser, allow multiple frontends etc, all at the same time.

Thaddy wrote

The link is for a very good scaling memorymanager over multi processor systems provided the software is also well written. Ivo's memorymanager is even lock free, if you use it properly.

I hadn't heard about TopMemory till now.

I read the PDF that comes in the download and it seems to be making quite a lot of the right noises.

The one thing that caught my eye that might or might not be reason to worry is this:

"Memory Usage

Part of the speedup that TopMemory achieves comes from allocating more memory then necessary and grouping allocations that are in the same sizerange. Therefore your application will use more memory when it runs. If you care more about low memory usage then TopMemory is not for you. It is optimized for performance at the cost of memory. Which is not usually a problem with the amounts of memory even regular PC’s have these days. "

There were a couple of charts showing how enredibly useful TopMemory could be when speed is the overriding factor, but no indication about how hungry it is for memory.

Any comments on that?

Cheers,

Adem

In our previous episode, Hans-Peter Diettrich said:

And Delphi (Windows!) users reported noticeable performance boosts (factor 3+), even if nobody ever came up with non-trivial example code, including fallbacks for restricted (32 bit) address space.

Yeah, and no wonder, most probably benchmarked against plain textfile I/O with its default 128 byte buffer.

One can actually spice FPC/Delphi text I/O up quite nicely with settextbuf to 8k (the last time I tested, in P4 3 GHz times, higher values didn't really matter anymore)

The compiler however already has its own 64k buffering system.

Adem wrote on Wed, 14 Jul 2010:

[snip]

Any comments on that?

This technique is well known and implemented by virtually all memory managers these days (it's called pooling, or freelists). FPC's default memory manager also does that (up to a certain allocation size).

Unless you create huge pools, it does not affect total memory much.

Jonas

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

Hans-Peter Diettrich wrote on Wed, 14 Jul 2010:

Apart from specific scenarios, memory mapping can easily be slower than direct reads. The main reason is that you get round trips to the OS via hardware interrupts whenever you trigger a page fault, instead of doing one or more (relatively cheap compared to interrupts) system calls. The potential savings of a few memory copies, especially for files in the range of 2-500kb, is very unlikely to compensate for this.

I see the biggest benefit in many possible optimization in the scanner and parser, which can be implemented *only if* an entire file resides in memory.

Then just read it into a buffer in one shot.

When memory management and (string) copies really are as expensive as some people say, then these *additional* optimizations should give the really achievable speed gain.

a) the memory management overhead primarily comes from allocating and freeing machine instruction (and to a lesser extent node tree) instances b) the string copy cost I mentioned primarily comes from getting symbol names for the purpose of generating rtti and assembler symbol names

Jonas

PS: please update the subject when changing the topic

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

I don't think we ever going to give an up front carte blanche for a massive rewrite to go into trunk. That is simply not sane.

ACK. I'm more concerned about work that is blacklisted for some reason.

Just this is hard to obey, when I see so many details that could be improved.

Will it do harm when I create more than one branch, e.g. one for general optimizations? Can other people contribute to such an branch as well?

DoDi

Even large pools are preferrable over chains of blocks, because following a chain can cause many page faults, at least it trashes the caches.

This is a known problem with garbage collectors (Java...), which can cause huge amounts of data being loaded into RAM, even if the current process actually doesn't use them. This is really bad for an garbage collector, which has been activated due to a shortage on memory - and it might be one reason for the use of compacting GC in .NET.

DoDi

Now that SSDs (which are near enough to random access memory) are getting to be cheap enough to be affordable for mainstream use (plus the much higher bandwidths of SATA3, USB3) is it feasible to further optimize IO speeds for the compiler at this stage?

Cheers,

Adem

In our previous episode, Hans-Peter Diettrich said:

> I don't think we ever going to give an up front carte blanche for a massive > rewrite to go into trunk. That is simply not sane. ACK. I'm more concerned about work that is blacklisted for some reason.

One reason the more to phase and modularize your efforts. It is less all or nothing.

As far as the blacklisting goes. There is only one way to counter skepticism. Show the goods, and it better be good.

Core is not unreasonable (*), but it will take more than simply pointing at some totally out of sync, totally overhauled branch, and saying "done".

Free Pascal is not a one way show, and that means cooperation and communication. People's opionions differ.

Keep in mind that running many branches long term will only increase the amount of management to keep them in sync, makes it more difficult to merge the finished results back etc.

Focus your efforts, on as small phases as possible.

And don't ever consider other people helping you in your planning, since it will nearly always be less than expected.

(*) well except me obviously, but I won't be reviewing compiler submissions,
so it is easier for me to say this all.

When the file resides in the OS file cache, no page faults will occur unless the file was removed from the cache. If not, every access request has to do disk I/O, resulting in process switching etc., so that the page faults are neglectable.

That's just what I suggested, for a first test :-)

May be, we'll see...

DoDi

These branches could be trashed again, when they proved useless or after merge into trunk. I could create separate projects in another repository as well, but these could not be merged back so easily.

Focus your efforts, on as small phases as possible.

ACK.

DoDi

Unless you are doing a cold compile, the main bottlenecks in the compiler are the memory manager (mostly the allocation of memory, freeing is faster), zero-filling new class instances (and partially resetting the register allocator) and tobject.initinstance.

I wonder if zeroing memory blocks (so when allocating them we know already that they contain zeros) and preparing new register allocators in a helper thread could improve this.

I see the biggest benefit in many possible optimization in the scanner and parser, which can be implemented *only if* an entire file resides in memory.

Include files, macro expansion and generics make such optimizations hard.

Rewriting the compiler in C ;)

Discuss the change on fpc-devel first, if you want to improve performance, generate numbers for at least:
make cycle
and
lazarus building.

No, but try to finish one thing and then start the next one. With increased time, patches might not apply automatically anymore.

Can other people contribute to such an branch as well?

Yes, just tell me to which branch and what login (I'll try to be faster this time ;)).

But if a memory block is freed and put back on the heap, you need to zero it again, so where is the gain in that ?

Michael.

While it's in the freelist, the helper task zeros it so when it is allocated again, it needs no zeroing again.

... thread ...

In our previous episode, Florian Klaempfl said:

But that then zeroes every deallocation.

Florian Klaempfl wrote on Thu, 15 Jul 2010:

I wonder if zeroing memory blocks (so when allocating them we know already that they contain zeros) and preparing new register allocators in a helper thread could improve this.

Possibly, yes. At least most OSes also zero pages in a background thread for exactly the same reasons.

I've also tried adding simple pooling systems to reduce the allocation/freeing time (a bit like mark/release), but the problem is that in many cases class instances can be either local or global (e.g., tai* can be added to some global stubs section or to a procedure's code, and parse tree nodes can become part of saved trees for inlining).

We could also parallelise writing out the assembler code for the external assembler, and possibly also some other list processing.

E.g., for N threads, start by simply walking over the list of instructions and store a pointer to the first and then every (list.count/N)th element (rounded up or down to the start of a new source line in case of the assembler writer). Then fire off the N threads to start processing the list at those points and let them store their output in temporary buffers. At the end, write the buffers out in the correct order.

There are currently some global dependencies (e.g. Darwin DWARF label numbers that are generated on the fly, and the current section type is kept track of for optimisation reasons), but it shouldn't be very difficult to resolve them. The same technique can probably also be used to parallelise at least parts of the internal assembler.

Especially when using DWARF, which causes a lot of tai constants to be generated, this could make a significant difference. And since the lists keep track of the number of elements, we can easily define a threshold used to decide whether to parallelise and if so, at most how many threads should be used.

Jonas

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

Marco van de Voort wrote on Thu, 15 Jul 2010:

But that then zeroes every deallocation.

You would only do this for class instances that are kept in a pool managed by overriding newinstance/freeinstance.

Jonas

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

Jonas Maebe wrote

a) the memory management overhead primarily comes from allocating and freeing machine instruction (and to a lesser extent node tree) instances

Did somebody take a look at FastMM for Delphi ? (
http://sourceforge.net/projects/fastmm/ )

Same seems to use a nice paradigm doing the Memory management for threaded applications.

-Michael

Hans-Peter Diettrich wrote on Thu, 15 Jul 2010:

Jonas Maebe schrieb:

[snip]

When the file resides in the OS file cache, no page faults will occur unless the file was removed from the cache. If not, every access request has to do disk I/O, resulting in process switching etc., so that the page faults are neglectable.

That is only true if you get at most as many page faults as you perform "read" system calls.

> Then just read it into a buffer in one shot. That's just what I suggested, for a first test :-)

Just increasing the buffer size by itself does not have any noticeable effects on the compilation speed (I benchmarked it in the past).

Those facts come from profiling runs. That does not mean that nothing can be optimised in the scanner/parser, but the bottleneck routines I posted are unrelated.

Jonas

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

Michael Schnell wrote on Thu, 15 Jul 2010:

Then please explain that paradigm, since apparently you already return, I will explain the FPC heap manager's paradigm: per thread, there is a separate heap manager so that in most cases no synchronisation is required. Only if memory is allocated in one thread and freed in another, then it will be added to a global locked structure. When a thread runs out of memory in its pools, it will first check this global (synchronised) structure before asking for more memory from the OS.

Jonas

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

Jonas Maebe wrote

Then please explain that paradigm, since apparently you already looked at it.

AFAIU, they use three areas for small midrange and large chunks

Small chunks are allocated in several lists, each of which hosts equally sized chunks, thus finding the chunks is a one-step access (no linked lists). Thus no unification of chunks when freeing is necessary. With a "normal" program some 98 % of the chunks are small.

Midrange Chunks are allocated in a single list of non equally sized chunks

Large chunks are allocated by a direct OS API call.

Only Midrange chunks implement "atomic" management for thread-safeness. For large chunks, the OS does this anyway, If a conflicting access is detected with small chunks, the second thread simply uses a midrange chunk in that rare occasion.

-Michael

Zitat von Jonas Maebe :

Does that mean, if I let a worker thread create strings, pass them to the main thread, free the worker thread and unreference the strings in the main thread the global structure will grow and grow?

Mattias

No, because the worker thread looks into the global structure when it runs out of "local" space.

Florian Klaempfl wrote

No, because the worker thread looks into the global structure when it runs out of "local" space.

This kind of garbage control might add some overhead at unforeseen times.

I seem to like the FASTMM paradigm better.

-Michael

On 07/15/2010 11:43 AM, Florian Klaempfl wrote: > No, because the worker thread looks into the global structure when it > runs out of "local" space. This kind of garbage control might add some overhead at unforeseen times.

You don't turn off caches in SMP systems either because sometimes it might need synchronization: in 99.9% of the use cases using caches is an advantage.

I seem to like

This has nothing to do with liking but simply with profiling your app and find out which memory manager fits best to the application.

Michael Schnell wrote on Thu, 15 Jul 2010:

On 07/15/2010 11:43 AM, Florian Klaempfl wrote: > No, because the worker thread looks into the global structure when it > runs out of "local" space. This kind of garbage control might add some overhead at unforeseen times.

And you will get overhead in the FASTMM scheme if you have two threads that are concurrently allocating and/or freeing a lot of small or medium blocks.

I seem to like the FASTMM paradigm better.

Both have their strong and weak points. Note that FPC's memory manager also keeps separate freelists for small blocks (but per thread).

Jonas

---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

Jonas Maebe wrote

And you will get overhead in the FASTMM scheme if you have two threads that are concurrently allocating and/or freeing a lot of small or medium blocks.

Only in extremely rare cases (which of course will be handled but seem not to be relevant regarding the overall speed).

With small blocks there is no concurrency (as in case of conflict, the second thread will use medium.

With medium of course there is concurrency, but as the need for handling medium blocks is a quite rare case - even if some small blocks are forced to the medium list due to a concurrency conflict - this does not harm much.

Both have their strong and weak points. Note that FPC's memory manager also keeps separate freelists for small blocks (but per thread).

I did not take a look at FPC's memory manager. Maybe someone might want to do some profiling ....

-Michael

Did you profiling? We did ...

With small blocks there is no concurrency (as in case of conflict, the second thread will use medium.

And the third and fourth thread?

In our previous episode, Michael Schnell said:

With small blocks there is no concurrency (as in case of conflict, the second thread will use medium.

I'm no memory manager expert, but reading this raises some question:

How is this conflict detected? If this is a kind of lock, (that needs to be SMP safe I guess) the FPC manager can probably skip that in most small allocations, and only has to do this if it really touches global structures?

Michael Schnell wrote

I did not take a look at FPC's memory manager. Maybe someone might want to do some profiling ....

I did the extensive profiling when working on fcl-xml package. For a single-threaded application, the following is true:

- FastMM is somewhat slower than FPC's memory manager, but the difference is small.
- Given the amount of source code in FPC and FastMM, FPC is clearly a winner :)
- A lot depends on how you deal with memory. It is much faster to allocate only than to allocate and release in turn.
- Given the above, a single forgotten 'const' modifier at function argument of type string may ruin your application performance irrespective of memory manager used.

Regards,
Sergei

Such initialized memory may reside in the wrong cache, on multi-core systems.

DoDi

Florian Klaempfl wrote

And the third and fourth thread?

Should not make much difference. The time span that is eligible for a conflict is very short and thus more than two threads at the same time that can't do the critical action in a normal way is extremely unlikely.

-Michael

Not necessarily. When all currently used files reside in memory, every (recorded) token can contain an pointer (or offset) into the file buffer. This may reduce the number of required string copies (not yet fully researched).

DoDi

A flag could be used to prevent zeroing at least at program shutdown (or the helper thread could be terminated).

DoDi

This is quite a lot ASM code, so I can't easily answer the question. I suppose you are right assuming that thread/SMP safety needs to be granted "somehow".

We might want to ask Pierre how he did it....

-Michael

With small blocks there is no concurrency (as in case of conflict, the second thread will use medium.

Just an idea: When the lists contain many entries, they could be split into buckets. Then the currently searched bucket(s) could be locked against use by other threads, which can skip them and inspect the next bucket.

DoDi

Sergei Gorelkin wrote

- FastMM is somewhat slower than FPC's memory manager, but the difference is small.

Good to know !

- Given the amount of source code in FPC and FastMM, FPC is clearly a winner :)

Yep. FastMM uses a lot ASM, so a plus for FPC RTL.

-Michael

I was curious about the differences about FastMM (which I use under Delphi) and TopMM, and asked about it in Delphi ThirdPartyTools NG.

FastMM is a lot more helpful WRT debugging user code, yet TopMM seems to have speed advantage for multi-threaded/multi-core application. [I haven't done any benchmarks.]

I was particularly interested in how 'Cross Thread performance hit' would affect applications --since TopMM mentions it as significant.

Here is the reply I got to that question.

[
nntp://forums.codegear.com/embarcadero.public.delphi.thirdpartytools.general/10280 ]

Arnaud BOUCHEZ wrote

> I could live with the others, but what excatly is 'Cross Thread

performance hit'; I mean, when (under what cirsumstances) would I fall for that?

The FastMM4 uses a LOCKed asm instruction for every memory allocation

or dis-allocation. This LOCK ensure that a memory is modified by only a thread at a time. This is the same LOCKed asm function which is used internally by Windows with its Critical Sections. Windows itself is told not to be very multi-core friendly, because it does use a lot of critical sections in its internal... Linux is much more advanced, and scales pretty well on massive multi-core architectures.

On a multi-core CPU, all cores just freeze in order to make this

LOCKed asm function threadsafe. If you have a lot of threads with more than one CPU, the context of every CPU core has to be frozen, cleared, all cores wait for the LOCKed asm instruction to complete, then the context is to be retrieved, and execution continue.

So a LOCK-free memory manager will improve "Cross Thread performance

hit" a lot.

One another big problem with the current implementation of the Delphi

compiler is that string types and dynamic arrays just use the same LOCKed asm instruction everywhere.

See what I wrote here (this post was not very popular, but indeed I

think I've raised a big issue on the Delphi compiler internals and performance here - and I don't think Embarcadero has plans to resolve this):

https://forums.codegear.com/thread.jspa?threadID=30826&tstart=90 IMHO if you use strings in your application and need speed, using

another memory manager than FastMM4 is not enough. You'll have to avoid most string use, and implement a safe TStringBuilder-like class. ShortStrings could be handy here, even if they are limited to 255 character long. In our enhanced RTL for Delphi 7, we avoid use of this LOCKed asm instruction if your application has only one thread: so if you use our enhanced RTL, and make thread by yourself (not using the TThread object), you'll have th e best multi-thread performance possible.

From this, I gather TopMM is a "GOOD THING"; and from Ivo's TopMM site, he seems to have intentions (TODO) to port TopMM to FPC.

I wonder if it would be a good idea to ask him to speed up that port.

Cheers,

Adem

You normally shouldn't ever need to process every token this way. Language keywords are encoded with enumeration type. Everything else is put into hashtable, so you typically need only as much string copies as there are distinct identifiers in the file. Besides, shortstring copies are pretty cheap, compared to AnsiStrings.

Regards,
Sergei

This is not true since at least Pentium Pro times. A lock prefix causes no bus lock anymore but only a cache lock.

Yes, without benchmarking it, we cannot know.

Such initialized memory may reside in the wrong cache, on multi-core systems.

I don't know about that. I think I recall reading that multi-core systems share L2 cache memory.

http://en.wikipedia.org/wiki/Multi-core_processor

I know Delphi used to initialize my data structures when I created them. I had to write custom Init and Done procedures for all my structures since switching to FPC. No to complain b/c it's a lot cleaner this way to keep track of Initialization and Finalization of data associated with each data struct.

That's okay, in detail when the uniquely cased names have to be stored.

Besides, shortstring copies are pretty cheap, compared to AnsiStrings.

I'm not sure about possible string operations, that force implicit conversion between Ansi and ShortString. I observed such performance hogs in Delphi and other languages, no experience with FPC and the concrete compiler code.

DoDi

Adem wrote

I was curious about the differences about FastMM (which I use under Delphi) and TopMM, and asked about it in Delphi ThirdPartyTools NG.

Thus TopMM seems excellently suited here.

I don't understand why in their Graphics, they imply that the Delphi 7 project uses FastMM.

Does TopMM have a license that allows for using it in The FP RTL ?

-Michael

I suppose their idea is that concurrent requests are so seldom that it is not helpful to implement anything better than just using medium size chunks. _Detecting_ the conflict is another issue, as potentially necessary atomic instruction might slow down the program a lot.

-Michael

Marco van de Voort wrote

Core is not unreasonable (*), (*) well except me obviously, but I won't be reviewing compiler submissions, so it is easier for me to say this all.

Sorry for the useless post, but this is just funny. ;)

Joost.

+1

Graeme.