Rash thoughts about .NET, C#, F# and Dynamics NAV.


"Every solution will only lead to new problems."

Friday, 24. October 2008


Using PLINQ in F# – Parallel Map and Reduce (Fold) functions – part 2

Filed under: .NET 3.0,English posts,F#,Informatik,PLINQ — Steffen Forkmann at 18:00 Uhr

Last time I showed how it is possible to use parallel map and fold functions to compute the sum of all factorials between 1 and 3000. The result was a nearly perfect load balancing for this task on a two processor machine. This time I will derive a generic function that computes partial results in parallel and folds them to a final result.

Let’s consider our F# example:

let add a b = a + b  
let fac (x:bigint) = 
  [1I..x] |> List.fold_left (*) 1I
let sequential() =
  [1I..3000I]
   |> List.map fac
   |> List.fold_left add 0I

This is the same as:

let calcFactorialSum min max =
  [min..max] 
   |> List.map fac
   |> List.fold_left add 0I  
 
let f1() = calcFactorialSum    1I 2000I
let f2() = calcFactorialSum 2001I 2200I
let f3() = calcFactorialSum 2201I 2400I
let f4() = calcFactorialSum 2401I 2600I
let f5() = calcFactorialSum 2601I 2800I
let f6() = calcFactorialSum 2801I 3000I
 
let sequential2() =
  f1() + f2() + f3() + f4() + f5() + f6()

We spitted the summation into 6 independent tasks and computed the sum of the partial results. This has nearly no bearing on the runtime.

But with the help of PLINQ we can compute each task in parallel:

let asParallel (list: 'a list) = 
  list.AsParallel<'a>()

let runParallel functions = 
    ParallelEnumerable.Select(
      asParallel functions, (fun f ->  f() ) )
 
let pFold foldF seed (data:IParallelEnumerable<'a>)=
  ParallelEnumerable.Aggregate<'a,'b>(
    data, seed, new Func<'b,'a,'b>(foldF))
 

let calcFactorialsParallel() =
  [f1; f2; f3; f4; f5; f6]
    |> runParallel
    |> pFold add 0I

This time we build a list of functions (f1, f2, f3, f4, f5, f6) and run them in parallel. "runParallel” gives us back a list of the partial results, which we can fold with the function “add” to get the final result.

On my Core 2 Duo E6550 with 2.33 GHz and 3.5 GB RAM I get the following results:

Time Normal: 26.576s

Time Sequential2: 26.205s (Ratio: 0.99)

Time “Parallel Functions”: 18.426s (Ratio: 0.69)

Time PLINQ: 14.990s (Ratio: 0.56) (Last post)

Same Results: true

We can see that the parallel computation of the functions f1 – f6 is much faster than the sequential.

But why is the PLINQ-version (see last post) still faster? We can easily see that each partial function needs a different runtime (e.g. it’s much harder to calculate the factorials between 2800 and 3000 than between 2000 and 2200). On my machine I get:

Time F1: 8.738s

Time F2: 2.663s

Time F3: 3.119s

Time F4: 3.492s

Time F5: 3.889s

Time F6: 4.442s

The problem is that the Parallel Framework can only guess each runtime amount in advance. So the load balancing for 2 processors will not be optimal in every case. In the original PLINQ-version there are only small tasks, and the difference between each runtime is smaller. So it is easier to compute the load balancing.

But of course we can do better if we split f1 into two functions f7 and f8:

let f7() = calcFactorialSum    1I 1500I
let f8() = calcFactorialSum 1501I 2000I

So we can get a better load balancing:

Time F1: 8.721s

Time F7: 4.753s

Time F8: 4.829s

Time Normal: 26.137s

Time “Parallel Functions”: 16.138s (Ratio: 0.62)

Same Results: true

Tags: , , , , , ,

Thursday, 23. October 2008


Using PLINQ in F# – Parallel Map and Reduce (Fold) functions – part 1

Filed under: .NET 3.0,C#,F# — Steffen Forkmann at 18:25 Uhr

If your wondering how Google computes query results in such a short time you have to read the famous “MapReduce”-Paper by Jeffrey Dean and Sanjay Ghemawat (2004). It shows how one can split large tasks into a mapping and a reduce step which could then be processed in parallel.

With PLINQ (part of the Parallel Extensions to the .NET Framework) you can easily use “MapReduce”-pattern in .NET and especially F#. PLINQ will take care of all the MultiThreading and load balancing stuff. You only have to give PLINQ a map and a reduce (or fold) function.

Lets consider a small example. Someone wants to compute the sum of the factorials of all integers from 1 to 3000. With List.map and List.fold_left this is a very easy task in F#:

#light
open System

let add a b = a + b
let fac (x:bigint) = [1I..x] |> List.fold_left (*) 1I

let sum =
  [1I..3000I]
    |> List.map fac
    |> List.fold_left add 0I

printfn "Sum of Factorials: %A" sum

Of course you could do much much better if you don’t compute every factorial on its own (I will show this in one of the next parts) – but for this time I need an easy function that is time consuming.

This simple Task needs 27 sec. on my Core 2 Duo E6550 with 2.33 GHz and 3.5 GB RAM.

But we can do better if we use parallel map and fold functions with help of PLINQ:

let pMap (mapF:'a -> 'b) (data:IParallelEnumerable<'a>) =
  ParallelEnumerable.Select(data, mapF)

let pFold foldF seed (data:IParallelEnumerable<'a>)=
  ParallelEnumerable.Aggregate<'a,'b>(
    data, seed, new Func<'b,'a,'b>(foldF))

Now we can easily transform our calculation to a parallel version:

let sum =
  [1I..3000I].AsParallel<bigint>()
    |> pMap fac 
    |> pFold add 0I

Putting all together we can write a small test application:

#light 
open System
open System.Linq
open System.Diagnostics

let testRuntime f =
  let watch = new Stopwatch()
  watch.Start()
  (f(),watch.Elapsed)

let add a b = a + b
let fac (x:bigint) = [1I..x] |> List.fold_left (*) 1I

let list = [1I..3000I]

let pMap (mapF:'a -> 'b) (data:IParallelEnumerable<'a>)=
  ParallelEnumerable.Select(data, mapF)

let pFold foldF seed (data:IParallelEnumerable<'a>)=
  ParallelEnumerable.Aggregate<'a,'b>(
    data, seed, new Func<'b,'a,'b>(foldF))

let PLINQ() =
  list.AsParallel<bigint>()
    |> pMap fac
    |> pFold add 0I

let sequential() =
  list
   |> List.map fac
   |> List.fold_left add 0I

let (sumSequential,timeSequential) =
  testRuntime sequential
printfn "Time Normal: %.3fs" timeSequential.TotalSeconds

let (sumPLINQ,timePLINQ) =
  testRuntime PLINQ
printfn "Time PLINQ: %.3fs" timePLINQ.TotalSeconds

timePLINQ.TotalSeconds / timeSequential.TotalSeconds
  |> printfn "Ratio: %.2f"

sumSequential = sumPLINQ
  |> printfn "Same Results: %A"

On my machine I get the following results:

Time Normal: 27.955s

Time PLINQ: 15.505s

Ratio: 0.55

Same Results: true

This means I get nearly a perfect load balancing on my two processors for this task.

In part II I describe how one can compute a series of functions in parallel.

Tags: , , , , , , ,

Monday, 2. April 2007


Googleplex Fotos

Filed under: Lustiges — Steffen Forkmann at 16:52 Uhr

Hier ein paar Links zu Fotosammlungen aus dem Google Headquarter. Manchmal hat man den Eindruck das ist ein bezahlter Trip in einen Freizeitpark.

Googleplex

Tags: , , , , ,

Massiver Betrug bei Google AdWords über "Suchportale"

Filed under: Counterize,Diverses — Steffen Forkmann at 14:30 Uhr

Vor gut einem Monat fielen mir in der Statistik der von mir betreuten Seite der S&H GmbH einige Ungereimtheiten auf. Durch mein Counterize II konnte ich sehen, dass in unregelmäßigen Abständen (aber ca. einmal pro Stunde) Besucher von ganz bestimmten Referer-Adressen kamen. Die Urprungsseiten waren irgendwelche “Suchportale”, die nur aus einem Suchfeld und Google-AdWords-Anzeigenblöcken bestanden. Die protokollierten Zugriffe kamen immer von unterschiedlichen IP’s, so dass ich am Anfang nicht an Betrug dachte.

Nach einer Weile jedoch stellte ich fest, dass NIE auch nur einmal auf der S&H-Seite irgendwo hin geklickt wurde. Auch der Suchbegriff der angeblich in dem Portal einmal pro Stunde eingegeben wurde, war sehr ungewöhnlich. Mein AdWords-Account sagt, dass dieser Begriff vielleicht alle 2 Wochen mal bei der normalen Google-Suche angeklickt wird. Jetzt stand für mich fest: Das sind keine “echten” Benutzer sondern Bot-Netzwerke, die auf Kosten der AdWords-Kunden reichlich Kohle abzocken.

Ich schaute also in meine AdWords-Einstellungen und versuchte die Seiten über das angebotene Tool zu blocken. Ohne Erfolg. Also schrieb ich eine Beschwerde an Google. Nach einigen langatmigen Mails stellte sich heraus, dass die betreffenden Portale keine AdSense-Anzeigen (Content-Werbenetzwerk) geschaltet haben, sondern Teil des offiziellen Google-Suchnetzwerkes sind.

“Unsere Techniker haben zweifelsfrei festgestellt, dass Ihre Anzeigen vom 1.
Februar bis zum 15. März nicht auf der von Ihnen übermittelten Seite im Content-Werbenetzwerk angezeigt wurden. Sie haben Ihre Anzeige auf dieser Seite gesehen, weil Sie Teil des Such-Werbenetzwerkes ist.”

Es gibt jedoch keine Möglichkeit Anzeigen für bestimmte Seiten im Suchnetzwerk zu blockieren. Man kann nur das gesamte Suchnetzwerk abschalten – das bedeutet dann aber auch keine Anzeigen mehr bei den großen Anbietern wie T-Online, Tiscali, Freenet, Chip.de usw.

Auf meine Beschwerde hin bestritt Google auch den Manipulationsverdacht und reagierte nur mit ewig langen vorgefertigten 0815-Standardmails. Zum Vorwurf, dass die gefakten Besucher in der Seite nicht herumklicken schreibt Google z.B.:

“Bitte beachten Sie, dass Besucher, die nur auf Ihre Zielseite klicken und nicht weiter in das Menü gehen, durchaus auch “echte”, also für Sie wichtige Besucher sein können und deshalb keine wertlosen Klicks verursachen. Beispielsweise informieren sich Besucher häufig kurz über die Zielseite einer Anzeige, speichern diese dann als Lesezeichen ab und kommen später wieder.”

Aha, also keine wertlosen Klicks. Für Google sicher nicht, denn Google verdient ja daran – deshalb kann ich auch auf eine Gutschrift über die zu Unrecht eingezogenen Beträge wahrscheinlich noch lange warten.

Interessante Artikel:

Tags: , , , ,

Thursday, 25. January 2007


Google PageRank Update in Gange

Filed under: Diverses,Google — Jens Hesse at 13:38 Uhr

Momentan aktualisiert Google offensichtlich den PageRank. Bei einigen Datacentern kann man den neuen PageRank schon abrufen. Der PageRank hat allerdings heutzutage eine untergeordnete Bedeutung. Viel wichtiger für eine Website ist eine gute Platzierung in den Suchergebnissen zu den relevanten Keywords. Der Navision Blog bekommt nun erstmals ein PR (4) zugewiesen.

Links:

Tags: , ,

Tuesday, 7. November 2006


Microsoft und der Suchmaschinenmarkt

Filed under: Diverses — Steffen Forkmann at 19:59 Uhr

Microsoft scheint jetzt wieder ernst zu machen und versucht den Suchmaschinenmarkt wieder etwas spannender zu gestalten. Neuste Projekte sind ja neben der eigentlichen Maschine (live.com) die wunderbare Ms. Dewey und seit gestern der Live Rundflug durch 15 Städte der USA über Virtual Earth 3D (SDK). Das ist schon wirklich beeindruckend Städte wie Las Vegas in der 3D-Ansicht zu betrachten. Selbstverständlich werden da kaum noch Weltraumaufnahmen benutzt, sondern hauptsächlich Aufnahme aus Flugzeugen und Vans.

Der Suchbegriff “pussy” geht auf Live.com übrigens immer noch nicht 😉

“Der Suchbegriff pussy führt möglicherweise zu rechtswidrigen oder jugendgefährdenden Inhalten.”

Der Cocktail “pussy foot” wird jedoch gefunden und nicht durch das Jugendschutz-Feature gefiltert.

In jedem Fall wird es spannend zu sehen wie sich Google zur neuen “Konkurrenz” verhält und ob die Google-Dienste (wie Google Earth, usw.) etwas vom Kuchen abgeben. Am wichtigsten wäre es meiner Meinung nach aber, dass sich endlich eine zweite Suchmaschine (egal von wem) am Markt positionieren könnte – so ein Monopol bei der Informationsbeschaffung ist zumindest bedenklich.

Tags: , ,

Google ändert seine Webmaster Richtlinien

Filed under: Diverses — Sebastian Wolf at 14:49 Uhr

Mit der Änderung von Googles Suchalgorithmen wurden auch die Richtlinien für Webmaster geändert. Früher wurden dynmische Seiten (also Seiten mit einem “?id=” in der url) nicht mit in den Index aufgenommen. Hier wird jetzt aber beschrieben, dass diese Seiten jetzt auch ohne URL-Rewriting in den Google-Index aufgenommen werden. Außerdem wird empfohlen die Parameterliste nicht zu lang werden zu lassen, da dies ein Problem für Bots darstelle. Es ist natürlich kein Fehler wenn man die Adressen trotzdem umschreibt, wenn man auch an andere Suchmaschinen denkt.

Tags: , ,

Saturday, 28. October 2006


Google’s "Twenty percent" time

Filed under: Diverses — Steffen Forkmann at 15:31 Uhr

Bei Google ist es Tradition, dass die Entwickler 20% ihrer Arbeitszeit (das ist ein ganzer Tag in der Woche) in Projekte stecken dürfen, die sie besonders interessieren und die so eigentlich nicht in ihrer Stellenbeschreibung stehen. Einige der neueren Google-Features (wie Gmail, Google News, AdSense und orkut) resultieren angeblich aus einigen dieser “überwachten” Hobbyprojekte. Nach Marissa Mayer, einer Abteilungsleiterin bei Google, kommen mittlerweile sogar 50% aller neuen Google-Features ursprünglich aus der “twenty percent”-Zeit.

Meiner Meinung nach ist das ein interessanter Ansatz, um den 5.ten Punkt (“Haben Sie Spaß an Ihrer Arbeit!”) meiner 10 Tipps für erfolgreiche Software-Entwicklung zu erfüllen und gleichzeitig der eigenen Firma auch noch Gewinn zu bringen – wie Google zeigt teilweise sogar extreme Gewinne.

Quellen:

  1. http://en.wikipedia.org/wiki/Google
  2. http://www.google.com/support/jobs/bin/static.py?page=about.html
  3. http://www.google.com/jobs/reasons.html
Tags: , ,