System.Collections.Generic.Dictionary = ¿Rendimiento máximo?

Question

Escribo un objetivo haXe C#, y he estado estudiando las diferencias de rendimiento para la biblioteca estándar de haXe, de modo que podamos ofrecer el mejor rendimiento posible a través de su código multiplataforma.

Un muy buen ejemplo es para el código de la tabla hash. Estaba un poco reacio a usar .NET's Dictionary, ya que parece voluminoso (las estructuras para los pares clave/valor pueden ocupar una gran cantidad de memoria debido a problemas de alineación de la memoria, además de la información innecesaria que contiene), y desde el estándar En la biblioteca no existe el hash de objetos, realmente pensé que podría exprimir un poco el rendimiento al no tener que llamar a GetHashCode, y alinearlo todo el tiempo.

También está claro que la implementación del diccionario utiliza una lista vinculada para hacer frente a las colisiones, lo que está lejos de ser ideal.

Así que comenzamos a implementar nuestra propia solución, comenzando con IntHash (Dictionary) Implementamos por primera vez Hopscotch hashing, pero realmente no salió muy bien, pero era obvio que no admitiría muy bien enormes tablas hash, ya que H es normalmente una palabra de máquina, y como H/Length aumenta, peor es el rendimiento.

Luego saltamos para implementar un algoritmo inspirado khash. Este tenía mucho potencial, ya que sus puntos de referencia son impresionantes y maneja las colisiones en la misma matriz. También tenía algunas cosas buenas, como cambiar el tamaño sin necesitar el doble de memoria que lo haríamos.

Los puntos de referencia fueron decepcionantes. Por supuesto, no hay necesidad de decir que el uso de memoria fue mucho menor en nuestra implementación que Dictionary. Pero también esperaba obtener un buen impulso en el rendimiento, pero ese no fue el caso, desafortunadamente. No estaba demasiado lejos, menos de un orden de magnitud, pero tanto para los conjuntos como para los get, la implementación de .NET aún funcionaba mejor.

Entonces mi pregunta es: ¿es eso lo mejor que tenemos para C#? Traté de buscar cualquier solución personalizada, y parece que no hay casi ninguna. Existe esa colección genérica de C5, pero el código está tan desordenado que ni siquiera probé. Y tampoco encontré un punto de referencia.

Entonces ... ¿Es eso? ¿Debo simplemente envolver el diccionario <>?

Gracias !!!

Answer 1

He encontrado que el .NET Dictionary funciona bien, si no excepcionalmente bien, en la mayoría de las situaciones. Es una buena implementación de propósito general. El problema con el que me encuentro con más frecuencia es el límite de 2 gigabytes. En un sistema de 64 bits, no puede agregar más de 89.5 millones de elementos a un diccionario (cuando la clave es un número entero o una referencia, y el valor es una referencia). La sobrecarga del diccionario parece ser de 24 bytes por artículo.

Ese límite se da a conocer de una manera muy extraña. El Dictionary parece crecer duplicando: cuando se llena, aumenta la capacidad hasta el siguiente número primo que es al menos el doble del tamaño actual. Por eso, el diccionario crecerá a unos 47 millones y luego arrojará una excepción porque cuando intenta duplicar (a 94 millones), la asignación de memoria falla (debido al límite de 2 gigabytes). Soluciono el problema asignando previamente el Dictionary (es decir, llamo al constructor que le permite especificar la capacidad). Eso también acelera al poblar el diccionario porque nunca tiene que crecer, lo que implica asignar una nueva matriz y volver a mezclar todo.

¿Qué le hace decir que Dictionary utiliza una lista vinculada para la resolución de colisiones? Estoy bastante seguro de que usa el direccionamiento abierto, pero no sé cómo funciona las sondas. Supongo que si realiza una prueba lineal, entonces el efecto es similar al que obtendría con una lista vinculada.

Escribimos nuestra propia clase BigDictionary para superar el límite de 2 gigabytes y descubrimos que un esquema de direccionamiento abierto directo con sondeo lineal proporciona un rendimiento razonablemente bueno. No es tan rápido como Dictionary, pero puede manejar cientos de millones de elementos (miles de millones si tuviera la memoria).

Dicho esto, usted debe ser capaz de escribir una tabla hash específica de la tarea más rápida que supera el diccionario .NET en algunas situaciones. Pero para una tabla hash de propósito general, creo que será difícil hacer algo mejor que lo que ofrece el BCL.

Answer 2

Hay muchas cosas que se deben tener en cuenta al diseñar una tabla hash "mejor". Una de las razones por las cuales los enfoques personalizados que probó fueron más lentos o no mejores que el.Diccionario neto es que muy a menudo la realización de una tabla hash es muy dependiente de:

• Los datos que están siendo hash
• El desempeño de la función hash
• El factor de carga de la mesa
• El número de colisiones contra los no-colisiones
• el algoritmo de resolución de colisiones
• la cantidad de datos en la tabla y cómo se almacena (por puntero/referencia o directamente dentro de los cubos)
• Los patrones de acceso a los datos
• El número de inserciones/deleciones vs recuperaciones
• La necesidad de cambiar el tamaño de un hash cerrada/abierta de implementación abordar
• y muchos otros factores ...

Con tantas cosas que modificar y sintonizar, es difícil, sin una cantidad significativa de esfuerzo, obtener una tabla hash general de alto rendimiento (tiempo y velocidad). Por eso, si va a tratar de crear una tabla hash personalizada en lugar de una integrada en una biblioteca estándar (como .NET), prepárese para pasar incontables horas y tenga en cuenta que su implementación bien ajustada solo se puede ajustar para el tipo específico y la cantidad de datos que has hashing.

Por lo tanto, no, el .NET Dictionary no es la tabla hash definitiva para ningún propósito específico. Pero, dada la frecuencia del uso del diccionario, estoy seguro de que el equipo de Microsoft BCL (Base Class Library) realizó una gran cantidad de perfiles para elegir el enfoque que eligieron para el caso general.