2009-12-13 41 views
69

Necesito llenar un byte[] con un solo valor distinto de cero. ¿Cómo puedo hacer esto en C# sin pasar por cada byte en la matriz?¿Cuál es el equivalente de memset en C#?

Actualización: Los comentarios parecen haber dividirla en dos preguntas -

  1. ¿Hay un método Marco para llenar un byte [] que podría ser similar a memset
  2. ¿Cuál es el más eficiente forma de hacerlo cuando se trata de una matriz muy grande?

Estoy totalmente de acuerdo en que el uso de un bucle simple funciona bien, como Eric y otros han señalado. El objetivo de la pregunta era ver si podía aprender algo nuevo sobre C# :). Creo que el método de Juliet para una operación paralela debería ser incluso más rápido que un simple bucle.

Puntos de referencia: , gracias a Mikael Svenson: http://techmikael.blogspot.com/2009/12/filling-array-with-default-value.html

Resulta que el lazo simple for es el camino a seguir, a menos que desee utilizar código no seguro.

Disculpas por no ser más claro en mi publicación original. Eric y Mark son correctos en sus comentarios; necesita tener preguntas más enfocadas con seguridad. Gracias por las sugerencias y respuestas de todos.

+0

Tenga en cuenta que para los bytes, la respuesta de Mark necesita una ligera modificación. byte [] image = Enumerable.Repeat ((byte) 255, [....]). ToArray(); De lo contrario, supondrá que desea int [] devuelto. – Jedidja

+1

Si tiene que ir por la ruta de rendimiento sospecho que usa inseguro/fijo y establece Int32 o Int64 a la vez y mover el puntero sería lo más rápido que puede lograr en C# (y usar un byte para los bytes restantes). –

+0

Buenos puntos sobre probar el rendimiento. Definitivamente lo haré :) – Jedidja

Respuesta

51

Usted podría utilizar Enumerable.Repeat:

byte[] a = Enumerable.Repeat((byte)10, 100).ToArray(); 

El primer parámetro es el elemento que desea que se repite, y el segundo parámetro es el número de veces que se repite la misma.

Esto está bien para matrices pequeñas, pero debe utilizar el método de bucle si se trata de arreglos muy grandes y el rendimiento es una preocupación.

+0

Hasta la votación. Aprendí algo :-) –

+1

Gracias :) Así que no es lo que me hubiera pasado por la cabeza para esta tarea .. – Jedidja

+36

Tenga en cuenta que esto va a ser decenas de veces más lento que simplemente escribir un bucle. La matriz en cuestión es de millones de elementos de largo; la preocupación por el rendimiento probablemente sea bastante pertinente. –

4

Se podía hacerlo al inicializar la matriz, pero no creo que eso es lo que está pidiendo:

byte[] myBytes = new byte[5] { 1, 1, 1, 1, 1}; 
+2

Eso sería correcto :) Estoy trabajando con imágenes por lo que el byte [] es varios cientos de miles/millones de elementos de gran tamaño. – Jedidja

11

Si el rendimiento es crítico, se podría considerar el uso de código no seguro y trabajando directamente con un puntero a la matriz.

Otra opción podría ser importar memset de msvcrt.dll y usar eso. Sin embargo, la sobrecarga de invocar eso fácilmente podría ser mayor que la ganancia en velocidad.

+2

Sí, es aproximadamente 40 veces más rápido que Repeat <> o for-loop. –

+0

Importando memset? Interesante ... tendré que darle una oportunidad. – Jedidja

+0

@jedidja Puede encontrar un ejemplo de código aquí: http://www.gamedev.net/community/forums/topic.asp?topic_id=389926 – Jan

10

Si el rendimiento es absolutamente crítico, entonces Enumerable.Repeat(n, m).ToArray() será demasiado lento para sus necesidades. Usted puede ser capaz de poner hacia fuera un rendimiento más rápido usando PLINQ o Task Parallel Library:

using System.Threading.Tasks; 

// ... 

byte initialValue = 20; 
byte[] data = new byte[size] 
Parallel.For(0, size, index => data[index] = initialValue); 
+1

Sí, gran observación y en realidad estamos usando Parallel.For else en otra parte para imagen código de procesamiento – Jedidja

+3

Sí, ¿pero no se siente sucio paralelizando el código de inicialización?!? ;) – kenny

+4

Este código es incorrecto tal como se presenta. El segundo parámetro de Parallel.For es toExclusive, lo que significa que el último byte de la matriz no se modifica. Cambiar 'tamaño - 1' a' tamaño'. –

20

Un poco tarde, pero el siguiente enfoque podría ser un buen compromiso sin volver a código no seguro. Básicamente, inicializa el comienzo de la matriz utilizando un bucle convencional y luego vuelve a Buffer.BlockCopy(), que debe ser lo más rápido posible con una llamada administrada.

public static void MemSet(byte[] array, byte value) { 
    if (array == null) { 
    throw new ArgumentNullException("array"); 
    } 
    const int blockSize = 4096; // bigger may be better to a certain extent 
    int index = 0; 
    int length = Math.Min(blockSize, array.Length); 
    while (index < length) { 
    array[index++] = value; 
    } 
    length = array.Length; 
    while (index < length) { 
    Buffer.BlockCopy(array, 0, array, index, Math.Min(blockSize, length-index)); 
    index += blockSize; 
    } 
} 
+2

@downvoter ¿Qué pasa con mi respuesta? ¿Alguna sugerencia para mejorar? – Lucero

+0

También vale la pena señalar que los parámetros de entrada de Buffer.BlockCopy (índices y longitudes) son índices y longitudes de matriz de bytes, por lo que para replicar esto en digamos array de enteros, necesita multiplicar los índices Buffer.BlockCopy y medirlos por sizeof (int) . –

18

Construyendo en Lucero's answer, aquí hay una versión más rápida.Duplicará el número de bytes copiados usando Buffer.BlockCopy en cada iteración. Curiosamente, lo supera en un factor de 10 cuando utiliza matrices relativamente pequeñas (1000), pero la diferencia no es tan grande para las matrices más grandes (1000000), aunque siempre es más rápido. Lo bueno de esto es que funciona bien incluso en arreglos pequeños. Se vuelve más rápido que el enfoque ingenuo en torno a la longitud = 100. Para una matriz de bytes de un millón de elementos, fue 43 veces más rápido. (probado en Intel i7, .Net 2,0)

public static void MemSet(byte[] array, byte value) { 
    if (array == null) { 
     throw new ArgumentNullException("array"); 
    } 

    int block = 32, index = 0; 
    int length = Math.Min(block, array.Length); 

    //Fill the initial array 
    while (index < length) { 
     array[index++] = value; 
    } 

    length = array.Length; 
    while (index < length) { 
     Buffer.BlockCopy(array, 0, array, index, Math.Min(block, length-index)); 
     index += block; 
     block *= 2; 
    } 
} 
10

Esta sencilla aplicación utiliza duplicación sucesiva, y se desempeña muy bien (aproximadamente 3-4 veces más rápido que la versión ingenua de acuerdo con mis puntos de referencia):

public static void Memset<T>(T[] array, T elem) 
{ 
    int length = array.Length; 
    if (length == 0) return; 
    array[0] = elem; 
    int count; 
    for (count = 1; count <= length/2; count*=2) 
     Array.Copy(array, 0, array, count, count); 
    Array.Copy(array, 0, array, count, length - count); 
} 

Editar: al leer las otras respuestas, parece que no soy el único con esta idea. Aún así, lo dejo aquí, ya que es un poco más limpio y funciona a la par con los demás.

+0

Escribí una publicación de blog sobre el uso de Array.Copía de esta manera. http://coding.grax.com/2011/11/initialize-array-to-value-in-c-very.html – Grax

6

Or use P/Invoke way:

[DllImport("msvcrt.dll", 
EntryPoint = "memset", 
CallingConvention = CallingConvention.Cdecl, 
SetLastError = false)] 
public static extern IntPtr MemSet(IntPtr dest, int c, int count); 

static void Main(string[] args) 
{ 
    byte[] arr = new byte[3]; 
    GCHandle gch = GCHandle.Alloc(arr, GCHandleType.Pinned); 
    MemSet(gch.AddrOfPinnedObject(), 0x7, arr.Length); 
} 
38

operación IL En realidad, no es poco conocida llamada Initblk (English version) que hace exactamente eso. Entonces, vamos a usarlo como un método que no requiere "inseguro". Aquí está la clase de ayuda:

public static class Util 
{ 
    static Util() 
    { 
     var dynamicMethod = new DynamicMethod("Memset", MethodAttributes.Public | MethodAttributes.Static, CallingConventions.Standard, 
      null, new [] { typeof(IntPtr), typeof(byte), typeof(int) }, typeof(Util), true); 

     var generator = dynamicMethod.GetILGenerator(); 
     generator.Emit(OpCodes.Ldarg_0); 
     generator.Emit(OpCodes.Ldarg_1); 
     generator.Emit(OpCodes.Ldarg_2); 
     generator.Emit(OpCodes.Initblk); 
     generator.Emit(OpCodes.Ret); 

     MemsetDelegate = (Action<IntPtr, byte, int>)dynamicMethod.CreateDelegate(typeof(Action<IntPtr, byte, int>)); 
    } 

    public static void Memset(byte[] array, byte what, int length) 
    { 
     var gcHandle = GCHandle.Alloc(array, GCHandleType.Pinned); 
     MemsetDelegate(gcHandle.AddrOfPinnedObject(), what, length); 
     gcHandle.Free(); 
    } 

    public static void ForMemset(byte[] array, byte what, int length) 
    { 
     for(var i = 0; i < length; i++) 
     { 
      array[i] = what; 
     } 
    } 

    private static Action<IntPtr, byte, int> MemsetDelegate; 

} 

¿Y cuál es el rendimiento? Aquí está mi resultado para Windows/.NET y Linux/Mono (diferentes PC).

Mono/for:  00:00:01.1356610 
Mono/initblk: 00:00:00.2385835 

.NET/for:  00:00:01.7463579 
.NET/initblk: 00:00:00.5953503 

Así que vale la pena considerarlo. Tenga en cuenta que el IL resultante no será verificable.

+0

¡Muy limpio! Gracias por compartir. – Jedidja

+3

Observé una diferencia mucho mayor. Para inicializar una matriz de 10MB 1000 veces, toma 0.5s con initblk y 22s con un loop. Aquí está mi punto de referencia: https://gist.github.com/thomaslevesque/6f653d8b3a82b1d038e1 –

+0

Eso es aún más interesante :) Con su punto de referencia mis resultados son: 3.66s vs 0.3s. –

5

Todas las respuestas solo escriben bytes individuales. ¿Qué ocurre si desea rellenar una matriz de bytes con palabras? ¿O flota? Encuentro uso para eso de vez en cuando. Así que después de haber escrito un código similar a 'memset' de forma no genérica varias veces y al llegar a esta página para encontrar un buen código para bytes individuales, escribí el método a continuación.

Creo que PInvoke y C++/CLI tienen sus inconvenientes. ¿Y por qué no tener el tiempo de ejecución 'PInvoke' para usted en mscorxxx? Array.Copy y Buffer.BlockCopy son ciertamente código nativo. BlockCopy ni siquiera es 'seguro': puede copiar una mitad larga sobre otra, o sobre un DateTime, siempre y cuando estén en matrices.

Al menos no iría a presentar un nuevo proyecto de C++ para cosas como esta: es casi una pérdida de tiempo.

Así que aquí está básicamente una versión extendida de las soluciones presentadas por Lucero y TowerOfBricks que se pueden usar para memset longs, ints, etc. así como para bytes individuales.

public static class MemsetExtensions 
{ 
    static void MemsetPrivate(this byte[] buffer, byte[] value, int offset, int length) { 
     var shift = 0; 
     for (; shift < 32; shift++) 
      if (value.Length == 1 << shift) 
       break; 
     if (shift == 32 || value.Length != 1 << shift) 
      throw new ArgumentException(
       "The source array must have a length that is a power of two and be shorter than 4GB.", "value"); 

     int remainder; 
     int count = Math.DivRem(length, value.Length, out remainder); 

     var si = 0; 
     var di = offset; 
     int cx; 
     if (count < 1) 
      cx = remainder; 
     else 
      cx = value.Length; 
     Buffer.BlockCopy(value, si, buffer, di, cx); 
     if (cx == remainder) 
      return; 

     var cachetrash = Math.Max(12, shift); // 1 << 12 == 4096 
     si = di; 
     di += cx; 
     var dx = offset + length; 
     // doubling up to 1 << cachetrash bytes i.e. 2^12 or value.Length whichever is larger 
     for (var al = shift; al <= cachetrash && di + (cx = 1 << al) < dx; al++) { 
      Buffer.BlockCopy(buffer, si, buffer, di, cx); 
      di += cx; 
     } 
     // cx bytes as long as it fits 
     for (; di + cx <= dx; di += cx) 
      Buffer.BlockCopy(buffer, si, buffer, di, cx); 
     // tail part if less than cx bytes 
     if (di < dx) 
      Buffer.BlockCopy(buffer, si, buffer, di, dx - di); 
    } 
} 

Teniendo esto simplemente puede añadir métodos cortos para tomar el tipo de valor que necesita para Memset con y llamar al método privado, por ejemplo,acaba de encontrar reemplazar ulong en este método:

public static void Memset(this byte[] buffer, ulong value, int offset, int count) { 
     var sourceArray = BitConverter.GetBytes(value); 
     MemsetPrivate(buffer, sourceArray, offset, sizeof(ulong) * count); 
    } 

O ir tonta y hacerlo con cualquier tipo de estructura (aunque el MemsetPrivate anterior sólo funciona para estructuras que el Mariscal a un tamaño que es una potencia de dos):

public static void Memset<T>(this byte[] buffer, T value, int offset, int count) where T : struct { 
     var size = Marshal.SizeOf<T>(); 
     var ptr = Marshal.AllocHGlobal(size); 
     var sourceArray = new byte[size]; 
     try { 
      Marshal.StructureToPtr<T>(value, ptr, false); 
      Marshal.Copy(ptr, sourceArray, 0, size); 
     } finally { 
      Marshal.FreeHGlobal(ptr); 
     } 
     MemsetPrivate(buffer, sourceArray, offset, count * size); 
    } 

He cambiado el initblk mencionado anteriormente para tomar ulongs para comparar el rendimiento con mi código y que silenciosamente falla - el código se ejecuta pero el búfer resultante contiene el byte menos significativo del ulong solamente.

Sin embargo, comparé la escritura de rendimiento como un gran buffer con for, initblk y mi método memset. Los tiempos son en total un total de más de 100 repeticiones escribiendo 8 bytes ulios, cualquiera que sea la cantidad de veces que se ajuste a la longitud del búfer. La versión for es desenrollada manualmente en bucle para los 8 bytes de un solo ulong.

Buffer Len #repeat For millisec Initblk millisec Memset millisec 
0x00000008 100  For 0,0032 Initblk 0,0107 Memset 0,0052 
0x00000010 100  For 0,0037 Initblk 0,0102 Memset 0,0039 
0x00000020 100  For 0,0032 Initblk 0,0106 Memset 0,0050 
0x00000040 100  For 0,0053 Initblk 0,0121 Memset 0,0106 
0x00000080 100  For 0,0097 Initblk 0,0121 Memset 0,0091 
0x00000100 100  For 0,0179 Initblk 0,0122 Memset 0,0102 
0x00000200 100  For 0,0384 Initblk 0,Memset 0,0126 
0x00000400 100  For 0,0789 Initblk 0,0130 Memset 0,0189 
0x00000800 100  For 0,1357 Initblk 0,0153 Memset 0,0170 
0x00001000 100  For 0,2811 Initblk 0,0167 Memset 0,0221 
0x00002000 100  For 0,5519 Initblk 0,0278 Memset 0,0274 
0x00004000 100  For 1,1100 Initblk 0,0329 Memset 0,0383 
0x00008000 100  For 2,2332 Initblk 0,0827 Memset 0,0864 
0x00010000 100  For 4,4407 Initblk 0,1551 Memset 0,1602 
0x00020000 100  For 9,1331 Initblk 0,2768 Memset 0,3044 
0x00040000 100  For 18,2497 Initblk 0,5500 Memset 0,5901 
0x00080000 100  For 35,8650 Initblk 1,1236 Memset 1,5762 
0x00100000 100  For 71,6806 Initblk 2,2836 Memset 3,2323 
0x00200000 100  For 77,8086 Initblk 2,1991 Memset 3,0144 
0x00400000 100  For 131,2923 Initblk 4,7837 Memset 6,8505 
0x00800000 100  For 263,2917 Initblk 16,1354 Memset 33,3719 

Excluí la primera llamada cada vez, ya que ambos initblk y memset toman un golpe de Creo que estaba a punto .22ms para la primera convocatoria. Ligeramente sorprendente, mi código es más rápido para llenar búferes cortos que initblk, ya que tiene media página llena de código de configuración.

Si alguien tiene ganas de optimizar esto, adelante realmente. Es posible.

0

Probado de varias maneras, descrito en diferentes respuestas. Ver fuentes de prueba en C# test class

benchmark report

3

Parece que System.Runtime.CompilerServices.Unsafe.InitBlock ahora hace lo mismo que la instrucción OpCodes.Initblk que menciona la respuesta de Konrad (también mencionó un source link).

El código para rellenar la matriz es como sigue:

byte[] a = new byte[N]; 
byte valueToFill = 255; 

System.Runtime.CompilerServices.Unsafe.InitBlock(ref a[0], valueToFill, (uint) a.Length); 
0

umm, objeto Array tiene un método llamado Clear. Estoy dispuesto a apostar que el método Clear es más rápido que cualquier código que escriba en C#.

Cuestiones relacionadas