c++ - compilador - gnu gcc compiler

Seguridad de std:: unordered_map:: merge()

Question

Mientras escribía algo de código dirigido a C ++ 17, me topé con un obstáculo que determinaba la excepción-seguridad de una operación que combina dos std :: unordered_maps compatibles. Según el borrador de trabajo actual, §26.2.7, la tabla 91 lee, en parte, con respecto a las condiciones de a.merge( a2 ) :

Requiere: a.get_allocator() == a2.get_allocator() .

Intenta extraer cada elemento en a2 e insertarlo en a función hash y un predicado de igualdad de teclas de a . En los contenedores con claves únicas, si hay un elemento en a clave equivalente a la clave de un elemento de a2 , ese elemento no se extrae de a2 .

Postcondiciones: los punteros y las referencias a los elementos transferidos de a2 refieren a esos mismos elementos pero como miembros de a . Los iteradores que se refieren a los elementos transferidos y todos los iteradores que se refieren a a se invalidarán, pero los iteradores a los elementos que permanecen en a2 seguirán siendo válidos.

Tiros: nada a menos que la función de hash o el predicado de igualdad de claves se lance.

Vale la pena señalar que estas condiciones recuerdan con creces las dadas para los requisitos de los contenedores asociativos ordinarios (std :: map), que figuran en §26.2.6, tabla 90, a.merge( a2 ) :

Requiere: a.get_allocator() == a2.get_allocator() .

Intenta extraer cada elemento en a2 e insertarlo en a objeto de comparación de a . En los contenedores con claves únicas, si hay un elemento en a clave equivalente a la clave de un elemento de a2 , ese elemento no se extrae de a2 .

Postcondiciones: los punteros y las referencias a los elementos transferidos de a2 refieren a esos mismos elementos pero como miembros de a . Los iteradores que se refieren a los elementos transferidos continuarán refiriéndose a sus elementos, pero ahora se comportan como iteradores en a , no en a2 .

Tiros: nada a menos que el objeto de comparación lance.

Necesitaba combinar dos std :: unordered_maps con la misma cantidad de elementos que podría asegurar que serían únicos en ambos contenedores, lo que significa que el mapa que contiene el resultado fusionado tendría el doble de elementos que tenía anteriormente, y el contenedor fusionado desde estaría vacío. Esto debería ser perfectamente seguro gracias a C ++ 17, ¿verdad?

Esta es una gran victoria en términos de rendimiento ... excepto, tenía esta duda persistente. Hilarantemente, la declaración posterior a la condición no dice nada acerca de si se respetaría o no el factor de carga máxima anterior en el mapa combinado, y si bien eso parece una suposición implícita segura, parece que está en conflicto ingenuo con la declaración sobre la excepción-seguridad de unordered_map. Si está utilizando un diseño de tabla hash en el que los depósitos se asignan de manera contigua a los búferes, mantener su factor de carga parecería implicar un nuevo lavado, lo que parece implicar la reasignación del búfer del depósito.

Ya, esto parecía un ejercicio de extrema observación de los ombligos y había una buena razón para dejarlo bastante bien: posiblemente se podría hacer una tabla de hash más complicada como una estructura completamente basada en nodos, similar a los árboles rojo-negros que usualmente sostienen la ETS. :: mapa, y en tal caso, la especificación parecía razonable, ya que una repetición no implicaría una asignación.

Quizás para mi beneficio, sucumbí a la duda y me interesé en la implementación de la fusión de gcc-7.1. Es increíblemente complicado, pero para resumir mis hallazgos, encontré que los cubos son, de hecho, asignados de manera contigua a los búferes, y el reabastecimiento implica una reasignación. Tal vez, pensé, había algo de magia más profunda que faltaba (observé la fuente durante casi un día entero y aún sentía que no lo entendía bien) que simplemente deshabilitó el reinicio durante una fusión, lo que significa que todas las condiciones especificadas se mantendría, pero podría obtener una regresión de rendimiento desagradable después de una fusión adecuadamente grande, ya que es probable que su mapa esté sobrecargado.

Solicité una evaluación práctica que refleja mi caso de uso (que habría presentado si fuera posible, lo siento), en lugar de cuestionar mi interpretación de libstdc ++:

#include <memory>        // for std::shared_ptr<>
#include <new>           // for std::bad_alloc
#include <utility>       // for std::move(), std::pair<>
#include <type_traits>   // for std::true_type
#include <unordered_map> // for std::unordered_map<>
#include <functional>    // for std::hash<>, std::equal_to<>
#include <string>        // for std::string
#include <iostream>      // for std::cout
#include <cstddef>       // for std::size_t

template<typename T>
class PrimedFailureAlloc
{
public:
  using value_type = T;
  using propagate_on_container_copy_assignment = std::true_type;
  using propagate_on_container_move_assignment = std::true_type;
  using propagate_on_container_swap = std::true_type;

  PrimedFailureAlloc() = default;

  template<typename U>
  PrimedFailureAlloc( const PrimedFailureAlloc<U>& source ) noexcept
    : m_triggered{ source.m_triggered }
  { }

  template<typename U>
  PrimedFailureAlloc( PrimedFailureAlloc<U>&& source ) noexcept
    : m_triggered{ std::move( source.m_triggered ) }
  { }

  T* allocate( std::size_t n )
  {
    if ( *m_triggered ) throw std::bad_alloc{};
    return static_cast<T*>( ::operator new( sizeof( T ) * n ) );
  }

  void deallocate( T* ptr, std::size_t n ) noexcept
  {
    ::operator delete( ptr );
  }

  bool operator==( const PrimedFailureAlloc& rhs ) noexcept
  {
    return m_triggered == rhs.m_triggered;
  }

  void trigger() noexcept { *m_triggered = true; }

private:
  template<typename U>
  friend class PrimedFailureAlloc;

  std::shared_ptr<bool> m_triggered{ new bool{ false } };
};

template<typename T>
bool operator!=( const PrimedFailureAlloc<T>& lhs,
                 const PrimedFailureAlloc<T>& rhs ) noexcept
{
  return !(lhs == rhs);
}

template< typename Key
        , typename T
        , typename Hash = std::hash<Key>
        , typename KeyEqual = std::equal_to<Key>
        >
using FailingMap = std::unordered_map<
  Key,
  T,
  Hash,
  KeyEqual,
  PrimedFailureAlloc<std::pair<const Key, T>>
>;

template<typename Key, typename T>
void printMap( const FailingMap<Key, T>& map )
{
  std::cout << "{/n";
  for ( const auto& [str, index] : map )
    std::cout << "  { " << str << ", " << index << " }/n";
  std::cout << "}/n";
}

int main()
{
  PrimedFailureAlloc<std::pair<const std::string, int>> a;
  FailingMap<std::string, int> m1{ a };
  FailingMap<std::string, int> m2{ a };

  m1.insert( { { "Purple", 0 }, { "Green", 3 }, { "Indigo", 16 } } );
  m2.insert( { { "Blue", 12 }, { "Red", 2 }, { "Violet", 5 } } );

  // m1.reserve( m1.size() + m2.size() );
  a.trigger();
  m1.merge( m2 );

  std::cout << "map :=/n";
  printMap( m1 );

  return 0;
}

Efectivamente, después de compilar este código bajo GCC-7.1, obtengo:

terminate called after throwing an instance of ''std::bad_alloc''
  what():  std::bad_alloc
[1]    10944 abort      ./a.out

Mientras que la línea 95 ( m1.reserve( m1.size() + m2.size() ); ), genera el resultado esperado:

map :=
{
  { Red, 2 }
  { Violet, 5 }
  { Purple, 0 }
  { Green, 3 }
  { Blue, 12 }
  { Indigo, 16 }
}

Entendiendo que C ++ 17 es todavía un borrador de estándar que aún no se ha finalizado, y que la implementación de gcc es experimental, supongo que mi pregunta sería:

1. ¿He malinterpretado gravemente la seguridad de la operación de fusión según lo establecido en la norma? ¿Existen prácticas recomendadas para usar std::unordered_map::merge() que me he perdido? ¿Se suponía que yo era el responsable implícito de garantizar la asignación de cubos? ¿Utilizará std::unordered_map::reserve() cuando Clang, MSVC e Intel finalmente sean compatibles con C ++ 17? Quiero decir, mi programa abortando cuando una fusión sin excepciones era imposible, después de alguna idea, se adhiere a las postcondiciones enumeradas ...
2. ¿Es esto realmente un defecto en la norma? La similitud de la redacción entre los contenedores asociativos no ordenados y los contenedores asociativos ordinarios podría haber permitido la introducción de garantías no intencionadas si el texto estuviera, por ejemplo, copiado.
3. ¿Es esto solo un error de gcc?

Vale la pena señalar que comprobé el rastreador de errores de gcc antes de este informe y que no encontré ningún error abierto que coincida con mi descripción, y además, revisé el informe de defectos estándar de C ++ y parecí haber quedado vacío la búsqueda de texto de ese sitio es agravante y puede que haya sido menos que exhaustivo). Lo último no es sorprendente, ya que los defectos estándar y sus soluciones o consecuencias generalmente se anotan en el código fuente de gcc y no encontré tales notaciones durante mi examen. Intenté compilar mi código de ejemplo en mi comprobación más reciente de clang (con más de una semana de antigüedad), pero el compilador no funcionó, por lo que seguí mi examen y no he consultado libc ++.

Answer 1

Esto es solo un defecto en el estándar, es decir, su posibilidad 2.

LWG acaba de mover el número 2977 de LWG al estado "Listo", lo que golpeará la cláusula de los lanzamientos erróneos.

Answer 2

Para comprender si la redacción en el estándar es correcta o no, debe examinar las funciones subyacentes.
Fusionarse consiste en dos operaciones.

• Configuración de punteros a elementos añadidos. Como ya están asignados, no hay asignación involucrada aquí.
• en caso de que se alcancen los límites para el número de elementos en el cubo, se llama rehash ()

Llamar a rehash () es un punto, donde se espera que se lance una excepción. Sol echemos un vistazo a su excepción de seguridad.

23.2.5.1 Garantías de seguridad de excepción [unord.req.except]
1 Para contenedores asociativos no ordenados, ninguna función clear () lanza una excepción. erase (k) no lanza una excepción a menos que la excepción sea lanzada por el objeto Hash o Pred del contenedor (si corresponde).
2 Para los contenedores asociativos no ordenados, si se produce una excepción por cualquier otra operación que no sea la función hash del contenedor desde dentro de una función de inserción o emplace que inserta un solo elemento, la inserción no tiene efecto.
3 Para los contenedores asociativos no ordenados, ninguna función de intercambio lanza una excepción a menos que esa excepción sea lanzada por el intercambio del objeto Hash o Pred del contenedor (si corresponde).
4 Para contenedores asociativos no ordenados, si se lanza una excepción desde dentro de una función rehash () diferente a la función hash o la función de comparación del contenedor, la función rehash () no tiene efecto.

Como se puede ver, la función rehash () está definida que no hace nada si se lanza una excepción al interior de otra que no sea la función de hash o de comparación. Esto es, en mi opinión, perfectamente en línea con la definición de fusión:

Tiros: nada a menos que la función de hash o el predicado de igualdad de claves se lance.

Mi entendimiento es que cuando no hay espacio para aumentar la estructura de datos subyacente para la lista de depósitos, entonces se mantiene en su forma original. Esto podría llevar a un acceso ligeramente ineficiente a los elementos, ya que podría haber más elementos en los grupos individuales que los definidos. Lo mismo puede suceder durante la inserción.

¿Dónde está el problema en tu caso? Posiblemente en la implementación de la función rehash () que tira donde no debería.

DESCARGO DE RESPONSABILIDAD: No soy un experto en el tema. Es justo lo que he encontrado. Así que siéntete libre de corregirme si estoy equivocado.