[C#] Byte na byte inlezen

[Neglacio]

Ik ben bezig aan een projectje die byte na byte inleest en markers plaatst waar het een bepaald patroon tegenkomt. Het bestand wordt "afgesplitst" op die markers en er wordt een Tiger-hash aan elk stukje toegekend. Op die manier zou het heel gemakkelijk zijn om "op afstand" te kijken hoe vergelijkbaar bestanden zijn door gewoon te zien welke stukken overeen komen aan de hand van die hashes.

Deze kleine algorithm heeft wel een grote bottleneck: De IO. Ik gebruik al reeds een BufferedStream, dus dit zou al geen probleem meer mogen zijn? Misschien vergeet ik enkele optimalisaties...
De code kan je hier weervinden: http://flox.svn.sourcefor...vc/flox/FloxNegC%23/Flox/
De IO wordt verzorgd door een BinaryReader die ik voor het gemak overerfde in een nieuwe klasse, zodat de BufferedStream automatisch wordt toegevoegd.

C#:

 using System.IO;

namespace Flox {
    /// <summary>
    /// Extends the <see cref="T:System.IO.BinaryReader"/> class with a <see cref="T:System.IO.BufferedStream"/>.
    /// </summary>
    class ByteReader : BinaryReader {
        /// <summary>
        /// Acts as a buffer for the size of the <see cref="T:System.IO.BufferedStream"/> to reduce calls.
        /// </summary>
        public long StreamSize { get; private set; }

        /// <summary>
        /// Makes it easier to read out the position of the <see cref="T:System.IO.BufferedStream"/>.
        /// </summary>
        public long Position {
            get {
                return base.BaseStream.Position;
            }
            set {
                base.BaseStream.Position = value;
            }
        }

        /// <summary>
        /// Standard constructor which loads a file into a <see cref="T:System.IO.BufferedStream"/> and a <see cref="T:System.IO.BinaryReader"/>.
        /// </summary>
        /// <param name="bestand">The path to the file.</param>
        public ByteReader(string bestand)
            : base((new BufferedStream(File.OpenRead(bestand)))) {
            StreamSize = base.BaseStream.Length;
        }
    }
}

[pedorus]

Ik zou waarschijnlijk performance aan het OS overlaten en met Memory-Mapped Files werken. Maar het is toch niet zo moeilijk om te kijken of je performance ongeveer overeenkomt met een programma als 7-zip?

[evolution536]

Ik snap wat je graag wilt doen, maar wat is nu eigenlijk je vraag?

[D-Raven]

pedorus schreef op vrijdag 25 november 2011 @ 12:37:
Ik zou waarschijnlijk performance aan het OS overlaten en met Memory-Mapped Files werken. Maar het is toch niet zo moeilijk om te kijken of je performance ongeveer overeenkomt met een programma als 7-zip?

Wist niet dat Memory-Mapped files eindelijk een managed API hebben in .Net 4

[Neglacio]

pedorus schreef op vrijdag 25 november 2011 @ 12:37:
Ik zou waarschijnlijk performance aan het OS overlaten en met Memory-Mapped Files werken. Maar het is toch niet zo moeilijk om te kijken of je performance ongeveer overeenkomt met een programma als 7-zip?

Thx! IO is a b*tch en dit kan me al een heel stuk verder helpen

@evolution536: Vraag was, hoe versnel ik de IO in C#?

[Hydra]

Neglacio schreef op vrijdag 25 november 2011 @ 14:18:
Thx! IO is a b*tch en dit kan me al een heel stuk verder helpen

@evolution536: Vraag was, hoe versnel ik de IO in C#?

Hoe snel is het nu en hoe verhoudt dat tot wat jij denkt dat het moet zijn? Bij puur bytes lezen is gewoon de HD de bottleneck normaliter.

Je class doet overigens helemaal niets dan zelf een bufferedstream toevoegen, en dat is eigenlijk redelijk nutteloos. Je laat niks zien van wat je verder met de data doet. Maak eerst maar eens een test waarbij je puur een bestand sequentieel inleest en meet hoe lang dat duurt. Op dit moment is er geen enkele indicatie dat op een of andere manier .Net de IO beperkt.

Edit, ik denk dat je probleem hier zit:

code:

public void Analyze() {
            byte[] b = new byte[_windowSize];
            // Sliding window

            Chunk c = new Chunk(0);
            int i = 0;
            while (i < Reader.StreamSize) {
                Reader.Position = i;
                Reader.Read(b, 0, b.Length);

                if (MatchSinglePattern(b)) {
                    c.ComputeHash();
                    Lib.Add(c);
                    c = new Chunk(i, b[0]);

                    byte[] skippedBytes = new byte[16384];
                    Reader.Read(skippedBytes, 0, skippedBytes.Length);
                    c.AddRange(skippedBytes);
                    i += 16384;
                } else {
                    c.Add(b[0]);
                }

                i++;
            }

            Lib.Add(c);
        }

Waarom je op die manier bytes leest, iedere keer de streamlength leest en iedere keer de position van de stream zet is me een raadsel. Maar dat is waar je performance issues zitten, en niet in de IO snelheid van .Net.

[ Voor 68% gewijzigd door Hydra op 25-11-2011 14:29 ]

[Dars123]

Ik ben bezig aan een projectje die byte na byte inleest

Je hoeft ook niet steeds byte-voor-byte een array van 16384 bytes van de disk te lezen, je kan toch alle bytes in een keer lezen en het patroon vanuit het geheugen checken?

@Hydra: dank voor de correctie, ik heb het inderdaad niet zo aandachtig bekeken.

[ Voor 32% gewijzigd door Dars123 op 25-11-2011 16:41 ]

[Hydra]

Dars123 schreef op vrijdag 25 november 2011 @ 16:10:
Je hoeft ook niet steeds byte-voor-byte een array van 16384 bytes van de disk te lezen, je kan toch alle bytes in een keer lezen en het patroon vanuit het geheugen checken?

Hij leest het ook niet byte voor byte in, hij leest afwisselend grote en kleine arrays in. Maar tussendoor reset hij steeds de stream naar een bepaalde positie. Het is gewoon een enorm rare constructie. Oh, en hij alloceeert ook iedere keer een array van 16kB.

[ Voor 5% gewijzigd door Hydra op 25-11-2011 16:23 ]

[Neglacio]

Ik test het patroon op een uitgelezen positie + de volgende 45 bytes (het sliding window van 46B), waarna de Stream de positie ook 46 stappen verder zet, terwijl ik gewoon elke keer counter + 45 wil lezen. De positie moet gewoon incrementen en niet het aantal uitgelezen bytes bij de positie optellen.

Als het patroon op die 46B past, dan is de counter het begin van een nieuwe Chunk. Elke volgende byte (en de 45 volgende) waar het patroon niet op past gaat in die Chunk naar een byte array. Die sla ik dan op zich opnieuw in een List.
Als en slechts als ik een match heb, dan sla ik al 16KB direct in de Chunk op om zoveel mogelijk overhead te vermijden, later in het project.

Direct X aantal bytes al uitlezen, als buffer, was ook mijn eerste gedacht maar ik dacht dit dus op te lossen met die BufferedStream.

Het lijkt misschien een rare constructie, maar het lijkt me het meest logische om het op deze manier te doen.

Die ByteReader-klasse heb ik puur toegevoegd om later nog aan uit te breiden. Maar dat is dus waar ik op vast zit.

[pedorus]

Even snel naar gekeken: Volgens mij gebruik je een rolling hash als een normale hash, ik kan me voorstellen dat dit 100% van 1 core trekt en de performance nogal tegenvalt. Effectief per byte overhevelen van data naar een Chunk lijkt me ook erg inefficiënt, dat kan beter in 1 keer of überhaupt niet. Aangezien de source van LBFS niet beschikbaar is (of misschien per mail), zou ik eens kijken naar http://code.google.com/p/rabinfingerprint/source/ . Het is java, maar de essentiële delen van de rolling hash zijn vrij eenvoudig om te zetten.

[Neglacio]

Ik heb zonet MemoryMappedFiles uitgeprobeerd, en er is zo goed als geen snelheidswinst te zien. In tegendeel, het is in mijn situatie tot 4 keer trager.

Ik vermoed wel meer en meer dat de Rabin Fingerprinting hier net het probleem geeft. Toch daar even op verder kijken

[pedorus]

MemoryMappedFiles zijn hier ook niet nodig, dat is iets voor random acces, en dat is hier niet echt van toepassing aangezien je vooral sequentieel leest. Ik weet verder ook niet wie je dat heeft aangepraat . Evenwel zou het eigenlijk nauwelijks verschil moeten maken, je gebruikt waarschijnlijk te veel api calls. Dan nog is dat dus niet het probleem hier.

Toch even over de file IO. Een BufferedReader op een FileStream zorgt voor een dubbele buffer. Als je een nieuwe FileStream aanmaakt dan kun je de buffer zetten. De standaard buffer van 4kb is te klein, ik zou 64 kb of 256 kb aanraden. Ik zou de boel openen zoals in dat artikel:

C#:

FileStream fs = new FileStream(fileName,    // name of file
                            FileMode.Open,          // open existing file
                            FileAccess.Read,    // read-only access
                            FileShare.None,     // no sharing
                            2 << 18,            // block transfer size = 256 KB
                            FileOptions.SequentialScan);    // sequential access

Vervolgens zou ik hier alleen maar blokken uit lezen naar een byte[] array (ook steeds gewoon 256 KB), en zeker nooit de positie zetten.

Over deze byte array bereken je dan de rolling hash, Ik mis trouwens ook een maximale grootte voor een Chunk, ik zou 64 KB nemen zoals LBFS dat doet, en hier niet per byte maar met maximaal 2 kopieën (splitsingsgrens buffer) werken. Zonder limiet levert een 4gb bestand met alleen maar 0-en een veel te grote Chunk op. Een Chunk kan trouwens prima worden doorgestuurd naar een andere Thread voor afhandeling (toevoegen aan BlockingCollection).

Maar goed, de rolling hash is waarschijnlijk het belangrijkst.

[Neglacio]

Hah, ik heb wat zitten prutsen, en blijkbaar is het zelfs die fingerprint niet die hier het grootste probleem was, noch dubbele buffers (een extra Bufferedstream met een veel kleinere capaciteit verdubbelde zelfs de snelheid ten opzichte van enkel een FileStream, mocht men verder niks doen met de data).

Het grootste probleem zat hem in het continu instellen van die position. Dit is nu gefixt, en het werkt al 12 keer sneller. Een 50MB bestand analyseren kost me nu nog maar 2.5 minuten in plaats van een half uur.

Nu verder kijken naar die hash. Maar sinds dat ik echt geen wiskundige achtergrond heb (en dit louter voor mijn plezier doe) weet ik echt niet wat er nog beter kan aan de huidige implementatie.

[Hydra]

Neglacio schreef op dinsdag 29 november 2011 @ 02:39:
Hah, ik heb wat zitten prutsen, en blijkbaar is het zelfs die fingerprint niet die hier het grootste probleem was, noch dubbele buffers (een extra Bufferedstream met een veel kleinere capaciteit verdubbelde zelfs de snelheid ten opzichte van enkel een FileStream, mocht men verder niks doen met de data).

Het grootste probleem zat hem in het continu instellen van die position. Dit is nu gefixt, en het werkt al 12 keer sneller. Een 50MB bestand analyseren kost me nu nog maar 2.5 minuten in plaats van een half uur.

Nu verder kijken naar die hash. Maar sinds dat ik echt geen wiskundige achtergrond heb (en dit louter voor mijn plezier doe) weet ik echt niet wat er nog beter kan aan de huidige implementatie.

Ik zei toch in mn reactie dat dat Position zetten verkeerd was?

[pedorus]

Neglacio schreef op dinsdag 29 november 2011 @ 02:39:
Nu verder kijken naar die hash. Maar sinds dat ik echt geen wiskundige achtergrond heb (en dit louter voor mijn plezier doe) weet ik echt niet wat er nog beter kan aan de huidige implementatie.

Het probleem is vrij simpel: in je huidige implementatie bereken je de hash steeds opnieuw 'from scratch' met alle 48(?) bytes waarvan je de hash wil hebben. In een goede implementatie voeg je steeds 1 byte toe aan de bestaande hash om de nieuwe hash te berekenen, wat een stuk sneller is omdat je bestaande informatie kan hergebruiken. Zie PushByte(), enkel dat zal je naar c# moeten vertalen.

[Neglacio]

@Hydra: Sorry voor de miskenning Ik dacht gewoon dat je dat aanwees als iets raars, met geen referentie naar de performance ervan. Je opmerking heb ik desalniettemin in acht genomen, bedankt daarvoor.

@Pedorus: Mooie opmerking. Ik had er nog niet echt diep op in gekeken, maar zou er uiteindelijk ook wel geraakt zijn. Dat is dus de bedoeling van de term "rolling hash". Thanks a lot!