Come posso rendere più veloce la scansione inversa di un file binario?

Question

Ho una specifica di file binario che descrive una struttura di dati a pacchetti. Ciascun pacchetto di dati ha un modello di sincronizzazione a due byte, così scansione per l'inizio di un pacchetto è possibile, utilizzando un BinaryReader e FileStream combinazione:

while(!reader.EndOfFile) 
{ 
    // Check for sync pattern. 
    if (reader.ReadUInt16() != 0xEB25) 
    { 
     // Move to next byte. 
     reader.BaseStream.Seek(-1, SeekOrigin.Current); 
     continue; 
    } 

    // If we got here, a sync pattern was found. 
} 

Questo processo funziona perfettamente bene in avanti, ma simile scansione del codice nella direzione opposta è almeno due ordini di grandezza più lento:

while(!reader.BeginningOfFile) 
{ 
    // Check for sync pattern. 
    if (reader.ReadUInt16() != 0xEB25) 
    { 
     // Move to previous byte. 
     reader.BaseStream.Seek(-3, SeekOrigin.Current); 
     continue; 
    } 

    // If we got here, a sync pattern was found. 
} 

ho provato un paio di soluzioni alternative, come spostare indietro di una quantità arbitraria (attualmente 1 megabyte) e la scansione in avanti, ma sta diventando chiaro che ciò che Ho davvero bisogno è un BinaryReader o FileStream che è modificato per caratteristiche di prestazione adeguate durante la lettura sia in avanti che in senso inverso.

ho già un FastFileStream che migliora le prestazioni in avanti leggere sottoclasse un ordinario FileStream e caching dei Position e Length proprietà (fornisce anche le proprietà BeginningOfFile e EndOfFile). Questo è ciò che guida la variabile reader nel codice sopra.

C'è qualcosa di simile che potrei fare per migliorare le prestazioni di lettura inversa, magari incorporando un MemoryStream come buffer?

Answer 1

L.B menzionato in un commento per utilizzare un file mappato in memoria, potresti rimanere impressionato dalle prestazioni.

Si prega di provare qualcosa di simile:

var memoryMapName = Path.GetFileName(fileToRead); 

using (var mapStream = new FileStream(fileToRead, FileMode.Open)) 
{ 
    using (var myMap = MemoryMappedFile.CreateFromFile(
          mapStream, 
          memoryMapName, mapStream.Length, 
          MemoryMappedFileAccess.Read, null, 
          HandleInheritability.None, false)) 
    {      
     long leftToRead = mapStream.Length; 
     long mapSize = Math.Min(1024 * 1024, mapStream.Length); 
     long bytesRead = 0; 
     long mapOffset = Math.Max(mapStream.Length - mapSize, 0); 

     while (leftToRead > 1) 
     { 
      using (var FileMap = myMap.CreateViewAccessor(mapOffset, 
           mapSize, MemoryMappedFileAccess.Read)) 
      { 
       long readAt = mapSize - 2; 
       while (readAt > -1) 
       { 
        var int16Read = FileMap.ReadUInt16(readAt); 
        //0xEB25 <--check int16Read here        
        bytesRead += 1; 
        readAt -= 1; 
       } 
      } 

      leftToRead = mapStream.Length- bytesRead; 
      mapOffset = Math.Max(mapOffset - mapSize, 0); 
      mapSize = Math.Min(mapSize, leftToRead); 
     } 
    } 
} 

Answer 2

EDIT: Okay, ho un po 'di codice. Bene, un bel po 'di codice. Ti permette di scorrere avanti e indietro per le intestazioni dei pacchetti.

Non garantisco che non ci siano errori, e si vuole assolutamente modificare la dimensione del buffer per vedere come si comporta ... ma dato lo stesso file che mi hai inviato, mostra almeno le stesse posizioni delle intestazioni dei pacchetti quando in avanti e all'indietro scansione :)

Prima il codice, mi sarebbe ancora suggerire che se si forse possibile, la scansione attraverso il file una volta e salvare un indice di informazioni del pacchetto per un uso successivo sarebbe probabilmente essere un approccio migliore.

Comunque, ecco il codice (completo di nessun test diverso dal programma di esempio):

PacketHeader.cs:

using System; 

namespace Chapter10Reader 
{ 
    public sealed class PacketHeader 
    { 
     private readonly long filePosition; 
     private readonly ushort channelId; 
     private readonly uint packetLength; 
     private readonly uint dataLength; 
     private readonly byte dataTypeVersion; 
     private readonly byte sequenceNumber; 
     private readonly byte packetFlags; 
     private readonly byte dataType; 
     private readonly ulong relativeTimeCounter; 

     public long FilePosition { get { return filePosition; } } 
     public ushort ChannelId { get { return channelId; } } 
     public uint PacketLength { get { return packetLength; } } 
     public uint DataLength { get { return dataLength; } } 
     public byte DataTypeVersion { get { return dataTypeVersion; } } 
     public byte SequenceNumber { get { return sequenceNumber; } } 
     public byte PacketFlags { get { return packetFlags; } } 
     public byte DataType { get { return dataType; } } 
     public ulong RelativeTimeCounter { get { return relativeTimeCounter; } } 

     public PacketHeader(ushort channelId, uint packetLength, uint dataLength, byte dataTypeVersion, 
      byte sequenceNumber, byte packetFlags, byte dataType, ulong relativeTimeCounter, long filePosition) 
     { 
      this.channelId = channelId; 
      this.packetLength = packetLength; 
      this.dataLength = dataLength; 
      this.dataTypeVersion = dataTypeVersion; 
      this.sequenceNumber = sequenceNumber; 
      this.packetFlags = packetFlags; 
      this.dataType = dataType; 
      this.relativeTimeCounter = relativeTimeCounter; 
      this.filePosition = filePosition; 
     } 

     internal static PacketHeader Parse(byte[] data, int index, long filePosition) 
     { 
      if (index + 24 > data.Length) 
      { 
       throw new ArgumentException("Packet header must be 24 bytes long; not enough data"); 
      } 
      ushort syncPattern = BitConverter.ToUInt16(data, index + 0); 
      if (syncPattern != 0xeb25) 
      { 
       throw new ArgumentException("Packet header must start with the sync pattern"); 
      } 
      ushort channelId = BitConverter.ToUInt16(data, index + 2); 
      uint packetLength = BitConverter.ToUInt32(data, index + 4); 
      uint dataLength = BitConverter.ToUInt32(data, index + 8); 
      byte dataTypeVersion = data[index + 12]; 
      byte sequenceNumber = data[index + 13]; 
      byte packetFlags = data[index + 14]; 
      byte dataType = data[index + 15]; 
      // TODO: Validate this... 
      ulong relativeTimeCounter = 
       (ulong)BitConverter.ToUInt32(data, index + 16) + 
       ((ulong)BitConverter.ToUInt16(data, index + 20)) << 32; 
      // Assume we've already validated the checksum... 
      return new PacketHeader(channelId, packetLength, dataLength, dataTypeVersion, sequenceNumber, 
       packetFlags, dataType, relativeTimeCounter, filePosition); 
     } 

     /// <summary> 
     /// Checks a packet header's checksum to see whether this *looks* like a packet header. 
     /// </summary> 
     internal static bool CheckPacketHeaderChecksum(byte[] data, int index) 
     { 
      if (index + 24 > data.Length) 
      { 
       throw new ArgumentException("Packet header must is 24 bytes long; not enough data"); 
      } 
      ushort computed = 0; 
      for (int i = 0; i < 11; i++) 
      { 
       computed += BitConverter.ToUInt16(data, index + i * 2); 
      } 
      return computed == BitConverter.ToUInt16(data, index + 22); 
     } 
    } 
} 

PacketScanner.cs:

using System; 
using System.Diagnostics; 
using System.IO; 

namespace Chapter10Reader 
{ 
    public sealed class PacketScanner : IDisposable 
    { 
     // 128K buffer... tweak this. 
     private const int BufferSize = 1024 * 128; 

     /// <summary> 
     /// Where in the file does the buffer start? 
     /// </summary> 
     private long bufferStart; 

     /// <summary> 
     /// Where in the file does the buffer end (exclusive)? 
     /// </summary> 
     private long bufferEnd; 

     /// <summary> 
     /// Where are we in the file, logically? 
     /// </summary> 
     private long logicalPosition; 

     // Probably cached by FileStream, but we use it a lot, so let's 
     // not risk it... 
     private readonly long fileLength; 

     private readonly FileStream stream; 
     private readonly byte[] buffer = new byte[BufferSize];   

     private PacketScanner(FileStream stream) 
     { 
      this.stream = stream; 
      this.fileLength = stream.Length; 
     } 

     public void MoveToEnd() 
     { 
      logicalPosition = fileLength; 
      bufferStart = -1; // Invalidate buffer 
      bufferEnd = -1; 
     } 

     public void MoveToBeforeStart() 
     { 
      logicalPosition = -1; 
      bufferStart = -1; 
      bufferEnd = -1; 
     } 

     private byte this[long position] 
     { 
      get 
      { 
       if (position < bufferStart || position >= bufferEnd) 
       { 
        FillBuffer(position); 
       } 
       return buffer[position - bufferStart]; 
      } 
     } 

     /// <summary> 
     /// Fill the buffer to include the given position. 
     /// If the position is earlier than the buffer, assume we're reading backwards 
     /// and make position one before the end of the buffer. 
     /// If the position is later than the buffer, assume we're reading forwards 
     /// and make position the start of the buffer. 
     /// If the buffer is invalid, make position the start of the buffer. 
     /// </summary> 
     private void FillBuffer(long position) 
     { 
      long newStart; 
      if (position > bufferStart) 
      { 
       newStart = position; 
      } 
      else 
      { 
       // Keep position *and position + 1* to avoid swapping back and forth too much 
       newStart = Math.Max(0, position - buffer.Length + 2); 
      } 
      // Make position the start of the buffer. 
      int bytesRead; 
      int index = 0; 
      stream.Position = newStart; 
      while ((bytesRead = stream.Read(buffer, index, buffer.Length - index)) > 0) 
      { 
       index += bytesRead; 
      } 
      bufferStart = newStart; 
      bufferEnd = bufferStart + index; 
     } 

     /// <summary> 
     /// Make sure the buffer contains the given positions. 
     /// 
     /// </summary> 
     private void FillBuffer(long start, long end) 
     { 
      if (end - start > buffer.Length) 
      { 
       throw new ArgumentException("Buffer not big enough!"); 
      } 
      if (end > fileLength) 
      { 
       throw new ArgumentException("Beyond end of file"); 
      } 
      // Nothing to do. 
      if (start >= bufferStart && end < bufferEnd) 
      { 
       return; 
      } 
      // TODO: Optimize this more to use whatever bits we've actually got. 
      // (We're optimized for "we've got the start, get the end" but not the other way round.) 
      if (start >= bufferStart) 
      { 
       // We've got the start, but not the end. Just shift things enough and read the end... 
       int shiftAmount = (int) (end - bufferEnd); 
       Buffer.BlockCopy(buffer, shiftAmount, buffer, 0, (int) (bufferEnd - bufferStart - shiftAmount)); 
       stream.Position = bufferEnd; 
       int bytesRead; 
       int index = (int)(bufferEnd - bufferStart - shiftAmount); 
       while ((bytesRead = stream.Read(buffer, index, buffer.Length - index)) > 0) 
       { 
        index += bytesRead; 
       } 
       bufferStart += shiftAmount; 
       bufferEnd = bufferStart + index; 
       return; 
      } 

      // Just fill the buffer starting from start... 
      bufferStart = -1; 
      bufferEnd = -1; 
      FillBuffer(start); 
     } 

     /// <summary> 
     /// Returns the header of the next packet, or null 
     /// if we've reached the end of the file. 
     /// </summary> 
     public PacketHeader NextHeader() 
     { 
      for (long tryPosition = logicalPosition + 1; tryPosition < fileLength - 23; tryPosition++) 
      { 
       if (this[tryPosition] == 0x25 && this[tryPosition + 1] == 0xEB) 
       { 
        FillBuffer(tryPosition, tryPosition + 24); 
        int bufferPosition = (int) (tryPosition - bufferStart); 
        if (PacketHeader.CheckPacketHeaderChecksum(buffer, bufferPosition)) 
        { 
         logicalPosition = tryPosition; 
         return PacketHeader.Parse(buffer, bufferPosition, tryPosition); 
        } 
       } 
      } 
      logicalPosition = fileLength; 
      return null; 
     } 

     /// <summary> 
     /// Returns the header of the previous packet, or null 
     /// if we've reached the start of the file. 
     /// </summary> 
     public PacketHeader PreviousHeader() 
     { 
      for (long tryPosition = logicalPosition - 1; tryPosition >= 0; tryPosition--) 
      { 
       if (this[tryPosition + 1] == 0xEB && this[tryPosition] == 0x25) 
       { 
        FillBuffer(tryPosition, tryPosition + 24); 
        int bufferPosition = (int)(tryPosition - bufferStart); 
        if (PacketHeader.CheckPacketHeaderChecksum(buffer, bufferPosition)) 
        { 
         logicalPosition = tryPosition; 
         return PacketHeader.Parse(buffer, bufferPosition, tryPosition); 
        } 
       } 
      } 
      logicalPosition = -1; 
      return null; 
     } 

     public static PacketScanner OpenFile(string filename) 
     { 
      return new PacketScanner(File.OpenRead(filename)); 
     } 

     public void Dispose() 
     { 
      stream.Dispose(); 
     } 
    } 
} 

programma .cs (per prova):

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Chapter10Reader 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      string filename = "test.ch10"; 

      Console.WriteLine("Forwards:"); 
      List<long> positionsForward = new List<long>(); 
      using (PacketScanner scanner = PacketScanner.OpenFile(filename)) 
      { 
       scanner.MoveToBeforeStart(); 
       PacketHeader header; 
       while ((header = scanner.NextHeader()) != null) 
       { 
        Console.WriteLine("Found header at {0}", header.FilePosition); 
        positionsForward.Add(header.FilePosition); 
       } 
      } 
      Console.WriteLine(); 
      Console.WriteLine("Backwards:"); 
      List<long> positionsBackward = new List<long>(); 
      using (PacketScanner scanner = PacketScanner.OpenFile(filename)) 
      { 
       scanner.MoveToEnd(); 
       PacketHeader header; 
       while ((header = scanner.PreviousHeader()) != null) 
       { 
        positionsBackward.Add(header.FilePosition); 
       } 
      } 
      positionsBackward.Reverse(); 
      foreach (var position in positionsBackward) 
      { 
       Console.WriteLine("Found header at {0}", position); 
      } 

      Console.WriteLine("Same? {0}", positionsForward.SequenceEqual(positionsBackward)); 
     } 
    } 
}