Slimmer algoritme voor splitten van data

[creator1988]

Ik heb een set met daarin ~ 70.000 verschillende Int32's (dwars door elkaar!). Deze Int32's wil ik verdelen in buckets, zodat er zo min mogelijk 'lege ruimtes' in zitten. Voorbeeld:

code:

     source = 1, 2, 4, 16, 17, 20

De adressen hierin zijn pointers. Ik wil dus de adressen 0x01, 0x02, 0x04, 0x16 etc. lezen. Omdat per item lezen verschrikkelijk duur is, ga ik bufferen.
Als ik nu 0x01 t/m 0x20 lees, lees ik heel veel bytes voor niets.

met een maximale lege ruimte van '5' worden dit 2 buckets met daarin:

code:

     bucket1 = 1, 2, 4
     bucket2 = 16, 17, 20

Nu doe ik 2 reads, 1 keer van 0x01 t/m 0x04, en een keer van 0x16 t/m 0x20. Ergo: sneller. Zeker als de ruimte tussen buckets gewoon 10 MB ofzo is.

Ik heb hiervoor een vrij naieve implementatie die het volgende doet:

- Sorteer lijst van laag - hoog
- Doorloop lijst
- Als verschil tussen vorige en huidige > 0x10000 -> nieuwe bucket
- Als bucketsize > 16 MB -> nieuwe bucket
- Voeg toe aan huidige bucket

Nadeel van deze approach:

- Sorteren van 70.000 int's die dwars door elkaar staan is érg duur (80% van CPU time ongeveer)

Ik heb naar Quick- en Mergesort's implementaties gekeken (ook parallel) maar vond geen snellere dan de standaard 'OrderBy' in Linq.

Weet iemand iets snellers? De buckets hoeven niet een 'perfecte' size te hebben ofzo, als ik hier wat tijdswinst pak, wil ik best meer buckets lezen. Ik accepteer ook dat er een aantal adressen in geen enkele bucket vallen (0,05% max. Daarna wordt het traag.).

C#:

        // memoryAddressList bevat circa 70.000 objecten
        // maxBufferSize is 16 * 1024 * 1024
        public static List<List<int>> SplitMemoryAddressesIntoBuffer(List<Int32> memoryAddressesList, int maxBufferSize)
        {
           // sorteer eerst
            memoryAddresses = memoryAddressesList.OrderBy(a => a).ToArray();

            // bepaal de laagste waarde
            int lowestPointer = memoryAddresses.First();
            // bepaalde hoogste waarde
            int highestPointer = memoryAddresses.Last();

            //holder voor mijn buckets
            List<List<int>> memoryAddressBatches = new List<List<int>>();

            // initialiseer wat waardes
            var currentAddressList = new List<int>();
            int previousAddress = lowestPointer - 1; // hierin stop ik laatst verwerkte item
            int lowestThisBatch = lowestPointer; // dit om te bepalen of we naar nieuwe bucket moeten
            
            // doorloop de hele lijst
            foreach(var mem in memoryAddresses)
            {
                // maak nieuwe bucket aan als verschil > 0x10000 of als de bucket groter is dan de maxSize
                if(mem - previousAddress > 0x10000  || mem - lowestThisBatch > maxBufferSize)
                {
                    memoryAddressBatches.Add(currentAddressList);
                    lowestThisBatch = mem;
                    currentAddressList = new List<int>();
                }
                // voeg toe aan huidige lijst
                currentAddressList.Add(mem);
                previousAddress = mem;
            }
            // voeg laatste bucket toe aan output
            memoryAddressBatches.Add(currentAddressList);
            #endregion

            // lege leeg gooien
            var batches = memoryAddressBatches.Where(m=>m.Count > 0).ToList();

            return batches;
        }

En voor those interested, het is hier voor: http://code.google.com/p/scoutframeworkfm2009/

[NMe]

Spoilers voor een techtopic waarin je daadwerkelijk geholpen wil worden? Handig. Ik heb ze weggehaald.

[RobIII]

Heel even simpel (ben op 't moment druk):
Volgens mij kun je heel simpel je buckets opbouwen (zonder dat je eerst de lijst nog hoeft te sorteren):

code:

foreach ptr in pointers
  bucket[ptr \ bucketsize] += ptr

Of mis ik iets?

/edit: In PHP even uitgewerkt:

PHP:

$pointers = array(1, 2, 4, 16, 17, 20);
$buckets = array();
$bucketsize = 5;

foreach ($pointers as $ptr)
  $buckets[(int)($ptr / $bucketsize)][] = $ptr;

var_dump($buckets);

array(3) {
  [0]=>
  array(3) {
    [0]=>
    int(1)
    [1]=>
    int(2)
    [2]=>
    int(4)
  }
  [3]=>
  array(2) {
    [0]=>
    int(16)
    [1]=>
    int(17)
  }
  [4]=>
  array(1) {
    [0]=>
    int(20)
  }
}

[ Voor 49% gewijzigd door RobIII op 23-09-2010 14:15 ]

[creator1988]

RobIII schreef op donderdag 23 september 2010 @ 14:11:
Heel even simpel (ben op 't moment druk):
Volgens mij kun je heel simpel je buckets opbouwen (zonder dat je eerst de lijst nog hoeft te sorteren):

code:

foreach ptr in pointers
  bucket[ptr \ bucketsize] += ptr

Of mis ik iets?

Ja, de maximale size van een bucket is 16 MB. Maar als ik

code:

waarde | 15 MB niets | waarde

Is het veel sneller om met 2 reads de losse waardes op te halen dan met één read 16 MB. Ik zit met heel veel loze ruimte op deze manier.

[ Voor 4% gewijzigd door creator1988 op 23-09-2010 14:14 ]

[RobIII]

creator1988 schreef op donderdag 23 september 2010 @ 14:14:

Is het veel sneller om met 2 reads de losse waardes op te halen dan met één read 16 MB. Ik zit met heel veel loze ruimte op deze manier.

Dan maak je eerst gewoon zoals ik beschreef (zie mijn edit ook even!) je buckets en ga je daarna zoiets doen:

code:

foreach bkt in buckets
  if (bkt.size==1)
    //single read
  else
    //block read

En eventueel nog wat meer optimalisaties. Je kunt nog alle kanten op; je zou zelfs de buckets een min/max property kunnen geven en aan de hand daarvan de max. read lengte kunnen bepalen en wanneer die aan voorwaarde X of Y voldoet een complete block read doen en anders de bucket a.d.h.v. de min/max waardes weer in een nieuwe serie kleinere buckets kunnen verdelen en zo kleinere blocken lezen of weer verdelen in kleinere buckets enz...

[ Voor 31% gewijzigd door RobIII op 23-09-2010 14:20 ]

[Soultaker]

creator1988 schreef op donderdag 23 september 2010 @ 14:05:
- Sorteren van 70.000 int's die dwars door elkaar staan is érg duur (80% van CPU time ongeveer)

Als dit het enige nadeel is: kun je dit kwantificeren? 70.000 getallen sorteren lijkt me peanuts (al geloof ik best dat het grootste deel van de tijd daarin gaat zitten, want de rest van je algoritme lijkt vrij efficiënt.) Het lijkt me dat dat nooit meer dan een seconde kan duren (en waarschijnlijk een stuk minder)?

Maar als je het sorteren echt sneller wil krijgen, dan zou ik RobIII's aanpak gebruiken. Dat is een soort radix sort. Het is niet optimaal qua aantal buckets/reads, maar dat was ook geen stricte eis.

[ Voor 15% gewijzigd door Soultaker op 23-09-2010 14:22 ]

[creator1988]

Soultaker schreef op donderdag 23 september 2010 @ 14:19:
[...]

Als dit het enige nadeel is: kun je dit kwantificeren? 70.000 getallen sorteren lijkt me peanuts (al geloof ik best dat het grootste deel van de tijd daarin gaat zitten, want de rest van je algoritme lijkt vrij efficiënt.) Het lijkt me dat dat nooit meer dan een seconde kan duren (en waarschijnlijk een stuk minder)?

Maar als je het sorteren echt sneller wil krijgen, dan zou ik RobIII's aanpak gebruiken. Dat is een soort radix sort. Het is niet optimaal qua aantal buckets/reads, maar dat was ook geen stricte eis.

Dit duurt in het meest nadelige geval zo'n 120 ms. op dit moment. Het moment van grote optimalisaties is wel voorbij

RobIII schreef op donderdag 23 september 2010 @ 14:17:
[...]

Dan maak je eerst gewoon zoals ik beschreef (zie mijn edit ook even!) je buckets en ga je daarna zoiets doen: ...

Ja, met een variant van radix sort gaat dit wellicht wel werken; al wordt het wel even zoeken naar de ideale waardes voor de bucketsizes. Ik ga het eens benchmarken.

[pedorus]

Het is een beetje onduidelijk wat de criteria hier zijn. Voldoet zoiets?

C#:

public static List<List<int>> SplitMemoryAddressesIntoBuffer(
    List<Int32> memoryAddressesList, int maxBufferSize)
{
    var buckets = new List<int>[0xFFFF];
    foreach (var mem in memoryAddressesList)
        (buckets[mem >> 16] ?? (buckets[mem >> 16] = new List<int>())).Add(mem);
    var result = new List<List<int>>();
    foreach (var bucket in buckets)
        if (bucket != null)
            if (bucket.Count <= maxBufferSize)
                result.Add(bucket);
            else
                for (int start = 0; start < bucket.Count; start += maxBufferSize)
                    result.Add(bucket.GetRange(start,
                        Math.Min(maxBufferSize, bucket.Count - start)));
    return result;
}

[RobIII]

pedorus schreef op donderdag 23 september 2010 @ 16:11:
Voldoet zoiets?

Als we toch aan 't optimaliseren zijn; je itereert hier (potentieel) over een shitload aan lege null buckets...

C#:

public static List<List<int>> SplitMemoryAddressesIntoBuffer(
    List<Int32> memoryAddressesList, int maxBufferSize)
{
    var buckets = new Dictionary<int, List<int>>();
    foreach (var mem in memoryAddressesList)
    {
        if (!buckets.ContainsKey(mem >> 4))
            buckets[mem >> 4] = new List<int>();
        buckets[mem >> 4].Add(mem);
    }
    var result = new List<List<int>>();
    foreach (var bucket in buckets.Values)
        if (bucket.Count <= maxBufferSize)
            result.Add(bucket);
        else
            for (int start = 0; start < bucket.Count; start += maxBufferSize)
                result.Add(bucket.GetRange(start,
                    Math.Min(maxBufferSize, bucket.Count - start)));
    return result;
}

En dan eventueel nog even een initieële capaciteit op de buckets specificeren om resizing te verminderen/voorkomen.

[ Voor 81% gewijzigd door RobIII op 23-09-2010 16:32 ]

[pedorus]

RobIII schreef op donderdag 23 september 2010 @ 16:21:
Als we toch aan 't optimaliseren zijn; je itereert hier (potentieel) over een shitload aan lege null buckets...

0xFFFF is niet zoveel, dus zelfs met deze testcase kom ik niet op een wezenlijk verschil (sterker nog het origineel is sneller met 3 milliseconden):

C#:

        static void Main(string[] args)
        {
            var s = Stopwatch.StartNew();
            var test = new List<int>() { 1, 2, 3, 0x10000, 0x10001, 0x10002 };
            var result = SplitMemoryAddressesIntoBuffer(test, 3);
            Console.WriteLine(s.ElapsedMilliseconds);
        }

Bij meer testdata gaat het verschil nog verder oplopen vanwege de lookups. Ik dacht nog wel aan een kortere en makkelijker te paralleliseren (?) versie (die nu natuurlijk nog een stuk trager is):

C#:

public static List<List<int>> SplitMemoryAddressesIntoBuffer(
    List<Int32> memoryAddressesList, int maxBufferSize)
{
    var result = new List<List<int>>();
    foreach (var buck in memoryAddressesList.GroupBy(mem => mem >> 16))
    {
       int i = 0;
       result.AddRange(buck.GroupBy(a => i++ / maxBufferSize).Select(a => a.ToList()));
    }
    return result;
}

[RobIII]

pedorus schreef op donderdag 23 september 2010 @ 16:48:
0xFFFF is niet zoveel, dus zelfs met deze testcase kom ik niet op een wezenlijk verschil (sterker nog het origineel is sneller met 3 milliseconden):

Hmmm, dat is dan tegen verwachting

pedorus schreef op donderdag 23 september 2010 @ 16:48:
Bij meer testdata gaat het verschil nog verder oplopen vanwege de lookups.

Hmmm; dat zou idd nog efficiënter moeten dan

[creator1988]

Robll's oplossing lijkt vrij goed te werken mits je met meer dan 4 bitshift. 20 gaat eigenlijk vrij goed.

code:

            int[] mem = new int[70000];
            Random r = new Random();
            for(int i = 0; i < mem.Length; i++)
            {
                mem[i] = r.Next(0xFFFFFFF);
            }

            Stopwatch co = new Stopwatch();
            Stopwatch ro = new Stopwatch();
            for(int i = 0; i < 10; i++)
            {
                co.Start();
                var cn = creatorOrigineel(mem, 16*1024*1024);
                co.Stop();

                ro.Start();
                var rn = robll(mem, 16 * 1024 * 1024);
                ro.Stop();

                Debug.WriteLine(string.Format("cn: {0} buckets, {1} bytes", cn.Count, cn.Sum(c => c.Max() - c.Min())));
                Debug.WriteLine(string.Format("rn: {0} buckets, {1} bytes", rn.Count,rn.Sum(c => c.Max() - c.Min())));
            }

            Debug.WriteLine("CO: " + co.Elapsed.TotalMilliseconds);
            Debug.WriteLine("Roblll: " + ro.Elapsed.TotalMilliseconds);

cn: 16 buckets, 268308593 bytes
rn: 256 buckets, 266431303 bytes
CO: 372,8269
Roblll: 64,9532

---

N.B. Geen representatieve set data, aangezien de data niet gegroepeerd is. Heb hier geen goede set bij de hand.

[ Voor 4% gewijzigd door creator1988 op 23-09-2010 17:19 ]

[pedorus]

creator1988 schreef op donderdag 23 september 2010 @ 17:18:
Robll's oplossing lijkt vrij goed te werken mits je met meer dan 4 bitshift. 20 gaat eigenlijk vrij goed.

4 was een foutje, had 16 moeten zijn (staat er ook )

RobIII schreef op donderdag 23 september 2010 @ 16:54:
Hmmm; dat zou idd nog efficiënter moeten dan

Een kleine optimalisatie daar is waarschijnlijk trygetvalue gebruiken (als in pedorus in "\[C#][discussie] Lekker veel var gebruiken?")
Dan nog is de code zonder Dictionary een stuk sneller (3x) in het 70000 random ints voorbeeld.

---

In het kader van parallellisatie: die laatste die ik postte kan trouwens misschien beter als:

C#:

        public static List<List<int>> SplitMemoryAddressesIntoBuffer(
            List<Int32> memoryAddressesList, int maxBufferSize)
        {
            var bucketsused = new int[0xFFFF];
            return memoryAddressesList.AsParallel().GroupBy(mem => (mem >> 16) |
               (((Interlocked.Increment(ref bucketsused[mem >> 16]) - 1) 
                 / maxBufferSize) << 16))
               .Select(a => a.ToList()).ToList();
        }

Maar ik heb geen idee hoe goed plinq werkt in dit soort gevallen en ik heb hier geen omgeving om het te testen. Misschien is iets als Parallel.ForEach sowieso handiger hier vanwege het beperkte aantal mogelijke keys (0xFFFF bij een 16-bits shift).

[creator1988]

pedorus schreef op donderdag 23 september 2010 @ 17:51:
[...]

4 was een foutje, had 16 moeten zijn (staat er ook )

[...]
Een kleine optimalisatie daar is waarschijnlijk trygetvalue gebruiken (als in pedorus in "\[C#][discussie] Lekker veel var gebruiken?")
Dan nog is de code zonder Dictionary een stuk sneller (3x) in het 70000 random ints voorbeeld.

---

In het kader van parallellisatie: die laatste die ik postte kan trouwens misschien beter als:

C#:

        public static List<List<int>> SplitMemoryAddressesIntoBuffer(
            List<Int32> memoryAddressesList, int maxBufferSize)
        {
            var bucketsused = new int[0xFFFF];
            return memoryAddressesList.AsParallel().GroupBy(mem => (mem >> 16) |
               (((Interlocked.Increment(ref bucketsused[mem >> 16]) - 1) 
                 / maxBufferSize) << 16))
               .Select(a => a.ToList()).ToList();
        }

Maar ik heb geen idee hoe goed plinq werkt in dit soort gevallen en ik heb hier geen omgeving om het te testen. Misschien is iets als Parallel.ForEach sowieso handiger hier vanwege het beperkte aantal mogelijke keys (0xFFFF bij een 16-bits shift).

PLinq heeft niet zoveel nut op sets die max. 100 ms duren, je threadsync kost zoveel tijd dat het efficienter is om gewoon 1 core dicht te trekken, in ieder geval dat zag ik eerder. Wellicht is het met een array met een vaste waarde makkelijker omdat je minder lockoverhead hebt. Heb hier geen .NET 4.

[pedorus]

creator1988 schreef op donderdag 23 september 2010 @ 18:08:
PLinq heeft niet zoveel nut op sets die max. 100 ms duren, je threadsync kost zoveel tijd dat het efficienter is om gewoon 1 core dicht te trekken, in ieder geval dat zag ik eerder. Wellicht is het met een array met een vaste waarde makkelijker omdat je minder lockoverhead hebt. Heb hier geen .NET 4.

Zie .oisyn in "\[C# threading] Waarom zijn m'n threads z..."

[roy-t]

Wat je eigenlijk wilt is en sorteeralgoritme dat in in O(n) kan sorteren, kijk eens naar bucket sort en maak daar een analoog van. Weet je bijvoorbeeld wel tussen welke waardes je pointers zitten?

[creator1988]

pedorus schreef op donderdag 23 september 2010 @ 18:11:
[...]

Zie .oisyn in "\[C# threading] Waarom zijn m'n threads z..."

Nou, wel in dit soort situaties:

code:

Parallel.ForEach(....) {
     i += 1;
     lock(syncrt) {
         lijstje.Add(i);
     }
}

en dat is wat we hier doen. Ik zou voor dit soort situaties een 'ThreadStatic' veld willen hebben, die gewoon in de scope van de methode leest en daarna makkelijk te unionen is.

[pedorus]

Ja, maar ik bedoel dus iets als (ongetest!):

C#:

public static List<List<int>> SplitMemoryAddressesIntoBuffer(
    List<Int32> memoryAddressesList, int maxBufferSize)
{
    var locks = new object[0xFFFF]; //or SpinLock?
    for (int i = 0; i < locks.Length; i++)
        locks[i] = new object();
    var buckets = new List<int>[0xFFFF];
    Parallel.ForEach(memoryAddressesList, mem =>
    {
        lock (locks[mem >> 16])
            (buckets[mem >> 16] ?? (buckets[mem >> 16] = new List<int>())).Add(mem);
    });
    var result = new List<List<int>>();
    foreach (var bucket in buckets)
        if (bucket != null)
            if (bucket.Count <= maxBufferSize)
                result.Add(bucket);
            else
                for (int start = 0; start < bucket.Count; start += maxBufferSize)
                    result.Add(bucket.GetRange(start,
                        Math.Min(maxBufferSize, bucket.Count - start)));
    return result;
}