Haskell Compilation Improvement

By: anon (anon.delete@this.anon.com),
Room: Moderated Discussions
Eric Bron (eric.bron.delete@this.zvisuel.privatefortest.com) on April 11, 2013 8:50 am wrote:
> > What does this mean?
> >
> > Single thread performance is very important quality, and increasingly
>
> fair enough, I'm mostly interested in multi thread peformance, I typically measured speedups
> in some rare occasions with explicit prefetch and a single thread but they all disapear with
> several threads (no slowdown due to the explicit prefetch, though, just a complete waste of
> development time), 8 concurrent threads sharing the LLC is the common case today
>
>
> > Prefetching can help a bit when traversing data structures which are not contiguous
> > in memory or at a predictable stride. Linked lists, trees, etc.
>
> do you have an example code to share ?

Not off hand.

> to make it work (i.e. prefetch several nodes
> ahead) you'll need an auxiliary array of pointers isn't it ? this looks very cumbersome
> to code and will waste bandwidth, particularly with 64-bit pointers

No. It is obviously difficult to do if you are traversing small objects in a very simple manner.

However if you traverse larger and more complex objects, for example, you may have known location of several memory addresses inherently in the object.

object = list.ptr;
prefetch(object->sub_object);
prefetch(&object->far_from_start);
prefetch(object->list.next);
/*
* At this point, you have 3 memops in flight. Even if do_something
* has to wait for one of them, you still get the MLP which probably
* can not be found by hardware prefetchers, and quite possibly will
* not be found so early by the OOOE machine.
*/
do_otherthing(object->sub_object);
do_something(&object->far_from_start);
object = object->list.next;
} while (object);

And now even better, we'll be able to prefetchw, which helps the above pattern quite a lot.
< Previous Post in ThreadNext Post in Thread >
Thread (96 posts)
TopicPosted ByPosted
Haskell Compilation ImprovementSymmetry
  Haskell Compilation ImprovementEric Bron
  Haskell Compilation ImprovementLinus Torvalds
    Haskell Compilation ImprovementEduardoS
      Haskell Compilation ImprovementLinus Torvalds
        Haskell Compilation ImprovementEduardoS
    Haskell Compilation Improvementβš›
      Haskell Compilation ImprovementEric Bron
        Haskell Compilation ImprovementBrendan
          Haskell Compilation ImprovementSymmetry
            Haskell Compilation ImprovementBrendan
          Haskell Compilation ImprovementEric Bron
            Haskell Compilation ImprovementBrendan
              Haskell Compilation ImprovementEric Bron
                Haskell Compilation ImprovementBrendan
                  Haskell Compilation ImprovementDavid Kanter
                    Software prefetching in JVMsGabriele Svelto
                  Haskell Compilation ImprovementEric Bron
                    Haskell Compilation ImprovementBrendan
                      Haskell Compilation ImprovementEric Bron
                        Haskell Compilation ImprovementBrendan
                          Haskell Compilation ImprovementEric Bron
                            Haskell Compilation ImprovementBrendan
                              Haskell Compilation ImprovementEric Bron
                                Haskell Compilation ImprovementBrendan
                                  Haskell Compilation ImprovementEric Bron
                          Haskell Compilation ImprovementEric Bron
                            Haskell Compilation ImprovementBrendan
                              Prefetch compilation testsEric Bron
        Haskell Compilation Improvementanon
          Haskell Compilation ImprovementMichael S
            Haskell Compilation Improvementanon
              Haskell Compilation ImprovementMichael S
                Haskell Compilation Improvementbakaneko
                  Haskell Compilation ImprovementEric Bron
                    Haskell Compilation Improvementbakaneko
                    Haskell Compilation Improvementanon
                      Haskell Compilation ImprovementEric Bron
                        Haskell Compilation Improvementanon
                          Haskell Compilation ImprovementEric Bron
                            Haskell Compilation Improvementanon
                              Haskell Compilation ImprovementEric Bron
                                Haskell Compilation ImprovementEric Bron
                                Haskell Compilation Improvementanon
                                  Haskell Compilation ImprovementEric Bron
                                    Haskell Compilation Improvementanon
                                      Haskell Compilation ImprovementEric Bron
                                        Haskell Compilation Improvementanon
                                          Haskell Compilation ImprovementEric Bron
                                  Prefetch *hints*Konrad Schwarz
                        Haskell Compilation ImprovementLinus Torvalds
                          Inherent advantage of software prefetchJouni Osmala
                            Inherent advantage of software prefetchSeni
                            Another example: software scatter gather (NT)Megol
                          Haskell Compilation ImprovementMaynard Handley
                            Haskell Compilation ImprovementTREZA
                              Haskell Compilation ImprovementMaynard Handley
                                Haskell Compilation Improvementanon
                                  Haskell Compilation ImprovementMaynard Handley
                                  Haskell Compilation Improvementbakaneko
                                Haskell Compilation ImprovementGabriele Svelto
                                  Haskell Compilation ImprovementMichael S
                                    Haskell Compilation ImprovementGabriele Svelto
                                    Haskell Compilation ImprovementTREZA
                            Haskell Compilation ImprovementMaynard Handley
                            Future core architectures. (Was Haskell Compilation Improvement)Maynard Handley
                              Speculative multi-threadingDavid Kanter
                                Speculative multi-threadingMaynard Handley
                              Future core architectures. (Was Haskell Compilation Improvement)Seni
                              Future core architectures. (Was Haskell Compilation Improvement)Linus Torvalds
                            Haskell Compilation ImprovementKonrad Schwarz
              Haskell Compilation ImprovementEric Bron
          Haskell Compilation ImprovementEric Bron
            Haskell Compilation ImprovementEugene Nalimov
              Haskell Compilation ImprovementEric Bron
                Haskell Compilation ImprovementEduardoS
            Haskell Compilation Improvementanon
              Haskell Compilation ImprovementEric Bron
                Haskell Compilation Improvementanon
                  Haskell Compilation ImprovementEric Bron
                    Haskell Compilation Improvementanon
                      Haskell Compilation ImprovementEric Bron
                        Haskell Compilation Improvementanon
                          Haskell Compilation ImprovementEric Bron
                            Haskell Compilation Improvementanon
                              Haskell Compilation ImprovementEric Bron
                                Haskell Compilation Improvementanon
                                  Haskell Compilation ImprovementEric Bron
                      Haskell Compilation ImprovementLinus Torvalds
                        Haskell Compilation Improvementanon
                        Haskell Compilation ImprovementRobert David Graham
        Software prefetch architecturePaul A. Clayton
          Software prefetch architectureEric Bron
            Software prefetch architectureMegol
              Software prefetch architectureEric Bron
  low barMichael S