std :: pair vs struct com dois de int

Question

Em um exemplo ACM, eu tive que construir uma grande mesa para programação dinâmica. Eu tinha para armazenar dois inteiros em cada célula, então eu decidi ir para um std::pair<int, int>. No entanto, a atribuição de uma enorme variedade deles levou 1,5 segundos:

std::pair<int, int> table[1001][1001];

Depois, eu mudei o código para

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

e a alocação tomou 0 segundos.

O que explica essa diferença enorme no tempo?

Answer 1

std::pair<int, int>::pair() construtor inicializa os campos com valores padrão (zero no caso de int) e seu struct Cell não (desde que você só tem um construtor padrão gerado automaticamente que não faz nada).

A inicialização requer escrevendo para cada campo que requer um monte de acessos de memória que são relativamente demorado. Com struct Cell nada for feito, em vez e não fazer nada é um pouco mais rápido.

Answer 2

As respostas até agora não explicam toda a magnitude do problema.

Como sharptooth tem as pontas, a solução par inicializa os valores de zero. Como Lemurik apontou, a solução par não é apenas inicializar um bloco contíguo de memória, em vez disso, está chamando o construtor par para cada elemento na tabela. No entanto, nem mesmo que faz explicá-lo a tomar 1,5 segundos. Outra coisa que está acontecendo.

Aqui está a minha lógica:

Assumindo que você estava em uma máquina antiga, dizem rodando a 1,33 GHz, em seguida, 1,5 segundos é 2E9 ciclos de relógio. Você tem 2E6 pares para construir, então de alguma forma cada construtor par está tomando 1000 ciclos. Não é preciso 1000 ciclos de chamar um construtor que apenas conjuntos de dois inteiros para zero. Não consigo ver como erros de cache faria demorar muito tempo. Eu acredito que se o número foi inferior a 100 ciclos.

Eu pensei que seria interessante ver onde mais todos esses ciclos de CPU está indo. Eu usei o crappiest mais antigo compilador C ++ que eu poderia encontrar para ver se eu poderia atingir o nível de desperdício necessário. Isso compilador foi VC ++ v6. No modo de depuração, ele faz algo que eu não entendo. Ele tem um grande loop que chama o construtor par para cada item na tabela - bastante justo. Esse construtor define os dois valores a zero - o suficiente justo. Mas antes de fazer isso, ele define todos os bytes em uma região 68 byte para 0xCC. Essa região é pouco antes do início da tabela grande. Em seguida, ele substitui o último elemento dessa região com 0x28F61200. Cada chamada do construtor par repete este. Presumivelmente, isso é algum tipo de contabilidade pelo compilador para que ele saiba quais regiões são inicializados quando a verificação de erros de ponteiro em tempo de execução. Eu adoraria saber exatamente o que isso é para.

De qualquer forma, isso explicaria onde o tempo extra está indo. Obviamente outro compilador pode não ser tão ruim. E, certamente, uma compilação de lançamento otimizado não seria.

Answer 3

Meu palpite é a maneira std :: pair é criado. Há mais sobrecarga durante a invocação de um construtor par 1001x1001 vezes do que quando você acabou de atribuir um intervalo de memória.

Answer 4

Estas são todas muito boas suposições, mas como todos sabem, suposições não são confiáveis.

Eu diria apenas aleatoriamente pausá-lo dentro que 1,5 segundos, mas você teria que ser muito rápido. Se você aumentou cada dimensão por um fator de cerca de 3, você poderia fazer com que demore mais como 10+ segundos, de modo que seria mais fácil para fazer uma pausa.

Ou, você pode obtê-lo sob um depurador, quebrá-lo no código construtor par, e depois única etapa para ver o que está fazendo.

De qualquer maneira, você teria uma resposta firme à pergunta, não apenas um palpite.

Answer 5

é realmente um bom exemplo sobre se deve escrever C ++ e uso STL com cuidado. quaisquer pensamentos?

meu projeto está trabalhando em uma ferramenta de teste de benchmark nível de código C & C ++ em que nós vamos fazer muitas amostras de código para descobrir o que é o código "bom" e o que é um "mau" hábito de codificação. consulte http://effodevel.googlecode.com para saber mais sobre C9B.M. planejamento. ninguém se você tinha experimentado lotes de tais casos, por favor, juntar-se ao projeto para ajudar-nos.