Validação de iterator
lsalamon
(STL).
Partindo do código abaixo, que simplifica a situação real onde o
problema se apresentou, tenho um problema que resolvi por
sincronização, pois o sistema é multithread.
map<string, string> map_test;
map<string, string>::iterator iter_map_test;
map_test [ "AAAAA" ] = "11111";
map_test [ "BBBBB" ] = "22222";
map_test [ "CCCCC" ] = "33333";
iter_map_test = map_test.find ("BBBBB"); // iterator esta apontando
para uma posição válida
map_test.erase ("BBBBB");// neste ponto o iterator deixa de ser
válido
A questão é como faço para verificar se o iterator iter_map_test é
válido ? Pois qualquer operação que tento a partir do momento que o
mesmo fica inválido causa uma excesão.
Obrigado a todos.
Felipe Magno de Almeida
Você nao faz. Se este é invalido, qualquer operacao com ele (exceto
copy-construction, destrucao e assignment)
sao invalidas.
Você deve tomar cuidado quais operacoes voce executa sobre o container
e quais iteradores vc tem com ele.
> Obrigado a todos.
--
Felipe Magno de Almeida
thoth39
> > A questão é como faço para verificar se o iterator iter_map_test é
> > válido ? Pois qualquer operação que tento a partir do momento que o
> > mesmo fica inválido causa uma excesão.
>
> Você nao faz. Se este é invalido, qualquer operacao com ele (exceto
> copy-construction, destrucao e assignment)
> sao invalidas.
--
P.
Felipe Magno de Almeida
Voce pode me apontar isto no padrao? Nao vejo como isto pode ser.
Voce nao esta confundindo o iterador retornado por end() com um
iterador invalido?
> --
>
>
> P.
Falou,
thoth39
> Voce pode me apontar isto no padrao? Nao vejo como isto pode ser.
> Voce nao esta confundindo o iterador retornado por end() com um
> iterador invalido?
Isso pode ser, sendo um iterador análogo a um ponteiro.
O que você não pode fazer com um ponteiro inválido é dereferenciá-lo
com * ou -> .
Porém, estou com muito sono pra ler o padrão agora e descobrir se essa
analogia é furada neste caso.
Ele está aqui na minha mesa, amanhã logo que eu acordar eu olho.
Provavelmente alguém vai ser mais rápido que eu, de qualquer modo. :-)
--
P.
Felipe Magno de Almeida
>
> On 5 abr, 02:30, "Felipe Magno de Almeida"
>
> <felipe.m.alme...@gmail.com> wrote:
>
>
> > Voce pode me apontar isto no padrao? Nao vejo como isto pode ser.
> > Voce nao esta confundindo o iterador retornado por end() com um
> > iterador invalido?
>
> Bem.
> Isso pode ser, sendo um iterador análogo a um ponteiro.
> O que você não pode fazer com um ponteiro inválido é dereferenciá-lo
> com * ou -> .
Bom, dei uma olhada. E quase nao aparece nada (C++03) para
invalid/invalidated/etcs.
Porem:
Em 24.1.3.1 temos:
— If a and b are equal, then either a and b are both dereferenceable
or else neither is dereferenceable.
Um iterador invalido me parece nao cumprir o requerimento de um
iterador nao-dereferenceable.
Por exemplo:
std::vector<char> v(10);
std::vector<char>::iterator end = v.end();
v.erase(boost::prior(v.end());
assert(v.end() == end); // Este assert dispara.
Acredito que um iterador invalido nao precisa cumprir nenhum
requerimento, exceto os de um objeto comum: Assignment e destruction.
Ateh copy-construction estou em duvida agora hehehe. Mas provavelmente eh ok.
> Porém, estou com muito sono pra ler o padrão agora e descobrir se essa
> analogia é furada neste caso.
Lol.
> Ele está aqui na minha mesa, amanhã logo que eu acordar eu olho.
Melhor uma versao eletronica pra buscas ;).
> Provavelmente alguém vai ser mais rápido que eu, de qualquer modo. :-)
>
> --
> P.
--
Felipe Magno de Almeida
Felipe Magno de Almeida
> 2008/4/5 thoth39 <pedro....@gmail.com>:
> >
>
> > On 5 abr, 02:30, "Felipe Magno de Almeida"
> >
> > <felipe.m.alme...@gmail.com> wrote:
> >
> >
> > > Voce pode me apontar isto no padrao? Nao vejo como isto pode ser.
> > > Voce nao esta confundindo o iterador retornado por end() com um
> > > iterador invalido?
> >
> > Bem.
> > Isso pode ser, sendo um iterador análogo a um ponteiro.
> > O que você não pode fazer com um ponteiro inválido é dereferenciá-lo
> > com * ou -> .
>
> Bom, dei uma olhada. E quase nao aparece nada (C++03) para
> invalid/invalidated/etcs.
> Porem:
C++0x diz em 24.1.10:
10 An invalid iterator is an iterator that may be singular.1)
E para singular em C++03 24.1.5:
5 Just as a regular pointer to an array guarantees that there is a
pointer value pointing past the last element of
the array, so for any iterator type there is an iterator value that
points past the last element of a corresponding
container. These values are called past-the-end values. Values of an
iterator i for which the expression *i
is defined are called dereferenceable. The library never assumes that
past-the-end values are dereferenceable.
Iterators can also have singular values that are not associated with
any container. [Example:
After the declaration of an uninitialized pointer x (as with int* x;),
x must always be assumed to have a
singular value of a pointer. ] Results of most expressions are
undefined for singular values; the only exception
is an assignment of a non-singular value to an iterator that holds a
singular value. In this case the singular
value is overwritten the same way as any other value. Dereferenceable
values are always nonsingular.
Em 24.1.1.2 na tabela:
X u(a); X post: u is a copy of a A destructor is assumed to be present
and accessible
Logo, ele pode ser destruido *e* assigned de um iterador valido.
O resto parece ser undefined behavior.
Thiago Adams
ou não.
Você esta guardando iteradores?
thoth39
> Logo, ele pode ser destruido *e* assigned de um iterador valido.
> O resto parece ser undefined behavior.
um iterador inválido.
Melhor simplesmente não permitir iteradores inválidos e pronto.
A própria definição de iterador inválido é muito frouxa.
--
P.
lsalamon
> requerimento, exceto os de um objeto comum: Assignment e destruction.
multithread, onde há um container que é acessado simultaneamente por
duas threads, uma que coloca e retira dados e outra que retira
somente.
Meu problema é que após o iterator ficar inválido não sei como testar
se ele está nesta condição. Como a operação não pode ser abortada,
tenho de saber se necessito reapontar o iterator, assim passei a usa-
lo em um bloco try/catch, capturando a exceção e reapontando o
iterator.
Acho que esta solução não é a mais adequada, pois exceções causam/
elevam o custo operacional e devem ser evitadas.
Mais uma vez obrigado pela ajuda.
On 5 abr, 03:05, "Felipe Magno de Almeida"
<felipe.m.alme...@gmail.com> wrote:
> 2008/4/5 thoth39 <pedro.lama...@gmail.com>:
>
>
> > On 5 abr, 02:30, "Felipe Magno de Almeida"
>
> > <felipe.m.alme...@gmail.com> wrote:
>
> > > Voce pode me apontar isto no padrao? Nao vejo como isto pode ser.
> > > Voce nao esta confundindo o iterador retornado por end() com um
> > > iterador invalido?
>
> > Bem.
> > Isso pode ser, sendo um iterador análogo a um ponteiro.
> > O que você não pode fazer com um ponteiro inválido é dereferenciá-lo
> > com * ou -> .
>
> Bom, dei uma olhada. E quase nao aparece nada (C++03) para
> invalid/invalidated/etcs.
> Porem:
>
> Em 24.1.3.1 temos:
Felipe Magno de Almeida
>
> > Acredito que um iterador invalido nao precisa cumprir nenhum
> > requerimento, exceto os de um objeto comum: Assignment e destruction.
>
> Esta situação de iterator inválido está ocorrendo em uma aplicação
> multithread, onde há um container que é acessado simultaneamente por
> duas threads, uma que coloca e retira dados e outra que retira
> somente.
>
> Meu problema é que após o iterator ficar inválido não sei como testar
> se ele está nesta condição. Como a operação não pode ser abortada,
> tenho de saber se necessito reapontar o iterator, assim passei a usa-
> lo em um bloco try/catch, capturando a exceção e reapontando o
> iterator.
Você deveria fortemente repensar seu design.
Primeiro que utilizar um iterador invalido nao gera uma exceção necessariamente.
Faze-lo gera undefined behavior, o que significa que *qualquer coisa*
pode acontecer.
> Acho que esta solução não é a mais adequada, pois exceções causam/
> elevam o custo operacional e devem ser evitadas.
Você deve estar usando o Visual C++ junto com SEH. Por isto as excessões.
Você precisa antes de mais nada sincronizar os acessos ao container
(se já nao está fazendo isso), com
a ajuda de um mutex, e deve considerar que *todos* os iteradores
criados fora de uma critical section
como invalidos. Desta forma você só pode utilizar iteradores que foram
criados em uma parte
de código protegida pelo mutex, onde nenhum acesso de outra thread
ocorreu sobre o container.
> Mais uma vez obrigado pela ajuda.
Felipe Magno de Almeida
Existem 2 defects reports sobre o assunto:
407 e 408.
Pelo 407, acho que nem copy-construction é permitido já que um
iterador singular (equivalente
a um iterador invalido) pode contar dados nao inicializados, e
copy-construction de
variaveis nao inicializadas possui undefined behavior.
Thiago Adams
problema basicamente de race condition.
A exceção que você recebe deve ser acesso inválido na memória e não
existe lógica a ser tratada neste caso, pois é um bug mesmo.
Você tem que focar a pergunta e colocar exemplos de como você pretende
acessar estes dois mapas em diferentes threads e que SO/lib está
usando.
lsalamon
diferente. Tenho de verificar como exatamente implementei o código no
trabalho.
Sei que estou usando estas macros do compilador VC8 :
//http://msdn2.microsoft.com/en-us/library/aa985973.aspx
#define _SECURE_SCL 1
#define _SECURE_SCL_THROWS 1
De qualquer forma, nos testes que fiz agora, fiz a seguinte tentativa
de validação do iterator :
long * lp = reinterpret_cast<long*>(&iter_map_test);
if ( * lp == 0 )
{
iter_map_test = map_test.begin();
}
Isto pode ser feito ?
Quais as inconseqüências de seu uso ?
Meu objetivo é reduzir ao máximo a necessidade de sincronização via
mutex/critical section, pois seria muito mais simples poder
simplesmente testar se o iterator continua válido ou não. Tenho de
pensar assim, pois posso ter uma situação onde o container poderá ter
mais de 500 elementos sendo colocados/retirados por ambas as threads.
O sistema tem ao todo 6 threads, mas o problema está ocorrendo somente
em uma.
Já descobri uma forma de tornar um iterator válido ao realizar uma
remoção de um elemento : map_test.erase(iter_map_test++);
Assim o iterator já retorna apontando para o próximo elemento ou para
end()
Meus testes foram com este código :
//------------------------------------------------------------------------------------
#define _SECURE_SCL 1
//http://msdn2.microsoft.com/en-us/library/aa985973.aspx
#define _SECURE_SCL_THROWS 1
#include <map>
#include <string>
#include <exception>
#include <iostream>
using namespace std;
void main(void)
{
map<string, string>::iterator iter_map_test;
map_test [ "AAAAA" ] = "11111";
map_test [ "BBBBB" ] = "22222";
map_test [ "CCCCC" ] = "33333";
iter_map_test = map_test.find ("BBBBB");
if ( * lp == 0 )
{
iter_map_test = map_test.begin();
}
map_test.erase ("BBBBB");
try
{
long * lp = reinterpret_cast<long*>(&iter_map_test);
if ( * lp == 0 )
{
iter_map_test = map_test.begin();
}
if ( iter_map_test == map_test.end() )
{
iter_map_test = map_test.begin();
}
if ( (*iter_map_test).first == "BBBBB" )
{
iter_map_test++;
}
}
catch ( exception & e )
{
cout << e.what() << endl;
}
catch ( ... )
{
cout << "generic exception." << endl;
}
}
//------------------------------------------------------------------------------------
Felipe Magno de Almeida
>
[snip]
> Já descobri uma forma de tornar um iterator válido ao realizar uma
> remoção de um elemento : map_test.erase(iter_map_test++);
> Assim o iterator já retorna apontando para o próximo elemento ou para
> end()
A lista ja explicou que nao eh possivel fazer o que voce quer, mas voce nao quer
ouvir a lista. Se voce decide ignorar os conselhos da lista, fica
dificil te ajudar.
[snip]
Blabos de Blebe
muitos também não.
Você poderia por favor, detalhar o cenário do seu problema.
Fique à vontade para responder em PVT se preferir.
2008/4/5 Felipe Magno de Almeida <felipe.m...@gmail.com>:
>
Leonardo Stabile
atual (C++03) desconhece threads, concorrência, os containers não são
thread-safe. Isso significa que seu problema não é de validação de
iteradores mas de concorrência de recursos. Você não pode omitir isso,
é bug. Mesmo que você "corrija" com alguma gambiarra de iterador,
amanhã ou depois quando você executar o código em outra máquina em
outras condições, o código terá outro erro. Não sei exatamente em que
condições essa área de memória está tendo acesso concorrente, mas
entre o tempo de você validar o iterador com sucesso e o utilizar,
outra thread pode invalidar a área de memória.
Thiago Adams
> Meu objetivo é reduzir ao máximo a necessidade de sincronização via
> mutex/critical section, pois seria muito mais simples poder
> simplesmente testar se o iterator continua válido ou não. Tenho de
> pensar assim, pois posso ter uma situação onde o container poderá ter
> mais de 500 elementos sendo colocados/retirados por ambas as threads.
conseguir pensar nas soluções.
Ajudaria esta lista a entrar um pouco nas discussões sobre multithread
que eu acho que ainda são poucas por aqui.
Não tem como apenas marcar o item como deletado mas sem remover? Se
você precisa adicionar e ler o mapa ao mesmo tempo é complicado. O
ideal é evitar isso e deixar uma thread com o controle do mapa as
outras so dizendo o que é para fazer mas sem ler o conteúdo.
> Já descobri uma forma de tornar um iterator válido ao realizar uma
> remoção de um elemento : map_test.erase(iter_map_test++);
> Assim o iterator já retorna apontando para o próximo elemento ou para
> end()
assim:
Map::iterator it = map.begin();
for (;it != map.end(); )
{
if (condition)
map.erase(it++);
else
++it;
}
Blabos de Blebe
enquanto se itera por ele?
2008/4/6 Thiago Adams <thiago...@gmail.com>:
Felipe Magno de Almeida
>
> Tem certeza que é seguro remover um elemento de um container
> enquanto se itera por ele?
Em todas as implementacoes da STL que eu conheça nao é seguro.
E é exatamente por este motivo que a STL nao oferece thread-safety
maior que a de um inteiro.
[snip]
Thiago Adams
On Apr 6, 5:31 pm, "Blabos de Blebe" <bla...@gmail.com> wrote:
> Tem certeza que é seguro remover um elemento de um container
> enquanto se itera por ele?
Aqui tem uma referencia:
http://www.sgi.com/tech/stl/Map.html
"Map has the important property that inserting a new element into a
map does not invalidate iterators that point to existing elements.
Erasing an element from a map also does not invalidate any iterators,
except, of course, for iterators that actually point to the element
that is being erased. "
Você acha outros exemplos na net também.
Outros containers retornam o iterator na operacao de erase que pode
ser usada para tornar o loop seguro para remoção. Como é o caso do
vector.
Cesar Mello
Alex Sandro Garzao
Você está com um problema sim de race condition. E o chato é que isso,
dependendo das características da implementação, pode não aparecer
frequentemente (aquele segfault que ocorre de tempos em tempos...).
Procura por race condition que certamente você vai encontrar o exemplo
clássico de manipulação de contas bancárias. Acho que com ele você vai
entender o problema.
Com relação ao seu projeto, como já citaram, existem algumas
abordagens. Se possível divulgue mais informações sobre o seu projeto
como quantidade de dados simultâneos, se tem um tempo de resposta
máximo, se o hardware onde vai rodar esse projeto tem "recursos
fartos" (se for rodar em hardware embarcado a conversa é outra...), e
qualquer outra informação que você achar pertinente.
Como o Thiago comentou, uma possibilidade é você deixar uma thread
responsável por alterações no conteiner (inserção, alteração,
exclusão). As outras threads realizam suas buscas/tarefas e, quando
necessário, solicitam alterações para a thread responsável por
alterações.
Outra abordagem seria colocar um mutex em cada registro, ou um mutex
associado a cada X registros. Com isso só a thread que tiver o mutex
pode manipular o dado. Mas isso depende muito da quantidade de
"registros" que você precisa manipular na memória em um tempo X.
Vou colocar 2 abordagens, mas elas dependem muito da quantidade de
dados simultâneos que você pode ter em um determinado momento dentro
do conteiner.
Trabalhei há um tempo atrás em um projeto similar ao seu, onde várias
threads podiam inserir alterar e excluir dados de um conteiner. O
número de threads era configurável, mas variava geralmente entre 8 e
16 (conforme a capacidade da máquina). Além disso, a quantidade de
informações que eu poderia ter simultaneamente era de aproximadamente
500.000 registros.
O tempo de resposta era fator crítico e o processamento realizado por
cada thread era praticamente o mesmo. Eu não tinha como deixar uma
thread apenas para manipular dados do conteiner porque senão ela
virava o gargalo do sistema. Além do que o hardware era um dual core
com 4 processadores.
Investimos um bom tempo tentando projetar uma arquitetura para
maximizar a concorrência entre as threads. Na época utilizamos um
pouco dos conceitos de buckets existentes no ORACLE. Para simplificar,
um bucket é um nome bonito para um conjunto de registros.
Definimos duas possíveis abordagens:
(1) Um hash (calculado sobre a chave de busca) que apontava para uma
lista de buckets. Esse hash não era extensível. O tamanho da lista de
buckets variava conforme a necessidade e a busca por um registro era
sequencial dentro dessa lista. Para cada lista existia um mutex
associado, ou seja, apenas uma thread podia manipular/percorrer os
dados dessa lista, mas outra thread poderia estar manipulando os dados
de outra lista de buckets.
(2) Um hash primário (calculado sobre a chave de busca) que apontava
para um hash secundário, e esse hash secundário apontava para o bucket
correto. Esse segundo hash era extensível. Neste caso existia um mutex
associado a cada bucket, e um no hash secundário para que uma thread
conseguisse acrescentar/remover buckets.
Como tinhamos uma interface bem definida para a forma de armazenamento
dos dados, era indiferente para o sistema a "abordagem de
armazenamento". Implementamos as duas abordagens e analizamos pontos
positivos e negativos. Pela análise que fizemos sobre as
características dos nossos dados, a gente optou pela primeira
abordagem.
Com mais informações sobre o seu projeto podemos ter melhores idéias :-)
Abraços !!!
[]'s
Alex Sandro Garzão
lsalamon
Conforme havia citado, o sistema já está em operação utilizando
sincronização com a implementação "Win32 Lightweight Lock" (http://
www.agileprogrammer.com/dotnetguy/archive/2001/12/10/4485.aspx).
De qualquer forma este problema me pareceu que poderia ser resolvido
de uma forma mais simples, para mim o fato de o iterator fical
inválido não poderia significar que não pude-se testar esta condição.
Veja que não sou um profundo conhecedor de STL.
Amanhã informarei exatamente qual é a exceção que estava sendo gerada.
thoth39
> responsável por alterações no conteiner (inserção, alteração,
> exclusão). As outras threads realizam suas buscas/tarefas e, quando
> necessário, solicitam alterações para a thread responsável por
> alterações.
Não compreendo como ela pode resolve o problema.
Se há uma thread responsável por atualizar um objeto esta thread se
torna, ela mesma, um recurso compartilhado.
Será necessário, em algum lugar, sincronização explícita entre todas
as outras threads que solicitam alterações a esta thread.
Haverá um mutex neste "requestUpdate(T const&)" .
Havendo um mutex na jogada, a existência de uma thread "servidora" me
parece espúria, visto que o objeto gerenciado poderia ter acessos não-
const sincronizados diretamente com este mutex.
Mesmo que a classe deste objeto seja impossível de alterar ainda assim
é possível um wrapper sincronizador.
O que eu não estou enxergando?
> Como tinhamos uma interface bem definida para a forma de armazenamento
> dos dados, era indiferente para o sistema a "abordagem de
> armazenamento". Implementamos as duas abordagens e analizamos pontos
> positivos e negativos. Pela análise que fizemos sobre as
> características dos nossos dados, a gente optou pela primeira
> abordagem.
Esta técnica das listas hash é interessante.
Parece haver uma troca entre o custo da sincronização e consequente
perda de concorrência e o acréscimo de mais uma busca no algoritmo.
Você tem medições de performance comparando as duas abordagens?
--
P.
Thiago Adams
On Apr 8, 1:44 pm, thoth39 <pedro.lama...@gmail.com> wrote:
> On 7 abr, 10:48, "Alex Sandro Garzao" <alexgar...@gmail.com> wrote:
>
> > Como o Thiago comentou, uma possibilidade é você deixar uma thread
> > responsável por alterações no conteiner (inserção, alteração,
> > exclusão). As outras threads realizam suas buscas/tarefas e, quando
> > necessário, solicitam alterações para a thread responsável por
> > alterações.
>
> Você poderia abrir mais a forma dessa solução?
> Não compreendo como ela pode resolve o problema.
>
> Se há uma thread responsável por atualizar um objeto esta thread se
> torna, ela mesma, um recurso compartilhado.
> Será necessário, em algum lugar, sincronização explícita entre todas
> as outras threads que solicitam alterações a esta thread.
>
> Haverá um mutex neste "requestUpdate(T const&)" .
>
> Havendo um mutex na jogada, a existência de uma thread "servidora" me
> parece espúria, visto que o objeto gerenciado poderia ter acessos não-
> const sincronizados diretamente com este mutex.
> Mesmo que a classe deste objeto seja impossível de alterar ainda assim
> é possível um wrapper sincronizador.
"Se você precisa adicionar e ler o mapa ao mesmo tempo é complicado.
O
ideal é evitar isso e deixar uma thread com o controle do mapa as
outras so dizendo o que é para fazer mas sem ler o conteúdo. "
caso contrário cai no mesmo problema.
thoth39
> "Se você precisa adicionar e ler o mapa ao mesmo tempo é complicado.
> O
> ideal é evitar isso e deixar uma thread com o controle do mapa as
> outras so dizendo o que é para fazer mas sem ler o conteúdo. "
>
> Só funciona com o detalhe que eu escrevi: "mas sem ler o conteúdo"
> caso contrário cai no mesmo problema.
Mas quem protege a thread de controle?
Como você sincroniza, entre todas as threads, a ordem de execução
destes "dizendo o que é para fazer"?
Duas threads podem fazer essa requisição ao mesmo tempo.
Este "dizer" deve tomar a forma de uma informação na memória
compartilhada entre as threads "clientes" e a thread de controle.
Como não controlar o acesso a essa memória com um mutex?
--
P.
Thiago Adams
Sim, ainda tem que ter um lock.
Mas a briga pelo lock é menor e o ideal que a operacao feita durante o
lock seja bem rapida. Por exemplo, a outra thread diz.. apaga este
item. O item entra numa fila de items para serem removidos. O lock
seria o tempo de colocar na lista e esta lista teria o lock.
O "find" do item que demora um pouco mais nao ficaria dentro deste
lock mas na thread principal que deleta o item.
thoth39
> > Como não controlar o acesso a essa memória com um mutex?
>
> Agora eu entendi o que não ficou claro...
> Sim, ainda tem que ter um lock.
> Mas a briga pelo lock é menor e o ideal que a operacao feita durante o
> lock seja bem rapida. Por exemplo, a outra thread diz.. apaga este
> item. O item entra numa fila de items para serem removidos. O lock
> seria o tempo de colocar na lista e esta lista teria o lock.
> O "find" do item que demora um pouco mais nao ficaria dentro deste
> lock mas na thread principal que deleta o item.
pequena, certo?
É uma solução interessante pra Associative Containers em geral.
--
P.
Thiago Adams
thread_mapa::remove(chave c)
{
Lock l(mutex);
m_toRemove.push_back(c);
}
thread_mapa::loop()
{
lista<chave> toRemove;
{
Lock l(mutex);
toRemove.swap(m_toRemove);
}
//parte demorada..
}
Alex Sandro Garzao
> > responsável por alterações no conteiner (inserção, alteração,
> > exclusão). As outras threads realizam suas buscas/tarefas e, quando
> > necessário, solicitam alterações para a thread responsável por
> > alterações.
>
> Você poderia abrir mais a forma dessa solução?
> Não compreendo como ela pode resolve o problema.
A thread responsável pelas modificações recebe as "tarefas" através de
uma lista, lista essa preenchida pelas outras threads. Essa lista sim
teria um mutex para inserir/remover tarefas. O tempo de cada lock deve
ser baixo para que essa arquitetura funcione com performance.
Seria, no final das contas, uma arquitetura produtor/consumidor, com a
ressalva que temos vários produtores para um consumidor, e o
consumidor é rápido o suficiente para consumir as N tarefas geradas
pelos produtores sem que o consumidor se torne o gargalo no sistema.
Bom, nada impede também que exista N consumidores :-)
Bom, propor arquiteturas é fácil, mas sem você ter uma idéia de como
os dados se comportam fica complicado. Nem que seja para você chegar a
conclusão que "não existe padrão" nos dados hehehe
> Esta técnica das listas hash é interessante.
> Parece haver uma troca entre o custo da sincronização e consequente
> perda de concorrência e o acréscimo de mais uma busca no algoritmo.
A gente aumentou o custo de processamento para uma busca, mas aumentou
o paralelismo real em máquinas SMP.
> Você tem medições de performance comparando as duas abordagens?
Não tenho mais esses dados precisamente :-/
Lembro que, com o nosso conjunto de dados, o desempenho era superior
nas buscas com hash duplo (meio óbvio) mas em toda uma bateria de
testes, o desempenho no final era inferior. Isso porque o segundo hash
é extensível e em determinado momento ele aumenta e/ou diminui o
número de entradas. Esse processo é muito caro computacionalmente
porque além do lock em todos esses buckets, se você altera o número de
buckets o hash deve ser recalculado para todas as chaves de todas os
buckets daquela hash secundário.
Para nós a versão com lista encadeada de buckets era, para uma bateria
de dados (aproximadamente 15 milhões de registros), aproximadamente
18% mais rápida. Se o número de registros simultâneos não variasse
muito pela linha do tempo, certamente o hash duplo seria bem mais
rápido.
[]'s
Alex Sandro Garzão
Alex Sandro Garzao
>
> "Se você precisa adicionar e ler o mapa ao mesmo tempo é complicado.
> O
> ideal é evitar isso e deixar uma thread com o controle do mapa as
> outras so dizendo o que é para fazer mas sem ler o conteúdo. "
>
> Só funciona com o detalhe que eu escrevi: "mas sem ler o conteúdo"
> caso contrário cai no mesmo problema.
Mil desculpas... Não foi intencional :-)
[]'s
Alex Sandro Garzão
Rodrigo Kumpera
thoth39
> Cheguei atrasado, mas implementações paralelas ou lock-free de hashtables
> existem. Por que não usar uma dessas em vez de todo esse samba com
> sincronização? Ou ainda, se quiser ainda usar essa técnica de uma mutator
> thread só, o queue de operações pode ser operado de maneira lock-free com
> contenção somente para operações que causem overflow no tamanho.
--
P.
Rodrigo Kumpera
E oque impende de se fazer uma implementação paralela de std::map?
thoth39
> E oque impende de se fazer uma implementação paralela de std::map?
> No mono temos uma estrutura que é próximo a um map ordenado e que precisa
> ser signal safe, aproveitamos para implementá-la de maneira a permitir
> execução paralela e lock-free. O resultado obviamente não é mais rápido que
> uma versão serial.
Não estamos falando sobre o que é possível, mas sobre o que é melhor
entre os possíveis.
Remover elementos de um std::map toma algum tempo; é desagradável que
muitas threads estejam bloqueadas em um mutex esperando para remover
um elemento em um std::map.
--
P.
Rodrigo Kumpera
Uma maneira muito simples de mitigar isso caso se saiba o domínio das chaves e que o acesso é espalhado entre ela é usar um array de maps onde cada um é responsável por um intervalo. O custo das operações aumenta por uma fração constante, porém é possivel ter leitura e escrita concorrente entre várias threads. Com uma tabela de hash é muito mais fácil fazer isso, porém.
Rodrigo
thoth39
> Uma maneira muito simples de mitigar isso caso se saiba o domínio das chaves
> e que o acesso é espalhado entre ela é usar um array de maps onde cada um é
> responsável por um intervalo. O custo das operações aumenta por uma fração
> constante, porém é possivel ter leitura e escrita concorrente entre várias
> threads. Com uma tabela de hash é muito mais fácil fazer isso, porém.
Esta solução foi proposta pelo colega Alex Sandro Garzão.
Dá uma lida no histórico desta conversa.
--
P.
Rodrigo Kumpera
Ele propos fazer isso com tabelas de hash, não estavamos falando std::map? ;)
A diferença é que no caso de usar hashing é muito mais facil garantir que a contenção será pequena dado que não precisa de qualquer conhecimento do dominio da chave.
lsalamon
ocorrendo e obtido via e.what(), era : [invalid map/set<T> iterator],
portanto uma condição com tratamento identificando a ocorrência
específica de iterador inválido.
Ou seja nada de invasão de memória.
Só foi possível disparar esta exceção configurando os seguintes
parâmetros na compilação (release):
#define _SECURE_SCL 1
#define _SECURE_SCL_THROWS 1
lsalamon
Cesar Mello
Amanda Cristina
André Tupinambá
> Pessoal,
>
> Sugestão, acho que é possível organizar este tópico e transformá-lo num
> artigo do wiki, não?
Se esse comentário fosse lá na empresa você teria acabado de receber
uma tarefa nova. :)
O nosso wiki é livre, logo...
Bom trabalho! :)
André
Marco Aurélio
2008/4/10 Amanda Cristina <amaz...@gmail.com>:
> Pessoal,
>
> Sugestão, acho que é possível organizar este tópico e transformá-lo num
> artigo do wiki, não?
Se esse comentário fosse lá na empresa você teria acabado de receber
uma tarefa nova. :)
Rodrigo Kumpera
Amanda Cristina
Parece que você foi voluntariada para essa tarefa. Que legal.
lsalamon
o motivo pelo qual minha indagação não pode ser atendida :
Porque não há como testar/saber se um iterator é válido.
Na verdade é muito simples, a partir do momento que um determinado
ítem, que está sendo referenciado por um iterator qualquer, for
deletado o iterator passa a apontar para uma área inválida.
Fazendo-se um exemplo com uma lista representa-se melhor o caso :
[1]-->[2]-->[3]-->[4]---...
/\
||
==== Iterator aponta para este
item [2] foi deletado :
______
| |
[1]-- --[3]---[4]---...
/\
||
==== Iterator aponta para área inválida
Por isto deve-se tomar muito cuidado com o uso de Iterator's,
inclusive encontrei muitas recomendações de que seu uso deve ser o
mais restrito possível.
On 4 abr, 22:25, lsalamon <lsala...@gmail.com> wrote:
> Olá, gostaria de uma ajuda para entender melhor como tratariterator
> (STL).
> Partindo do código abaixo, que simplifica a situação real onde o
> problema se apresentou, tenho um problema que resolvi por
> sincronização, pois o sistema é multithread.
>
> map<string, string> map_test;
> map<string, string>::iteratoriter_map_test;
>
> map_test [ "AAAAA" ] = "11111";
> map_test [ "BBBBB" ] = "22222";
> map_test [ "CCCCC" ] = "33333";
>
> iter_map_test = map_test.find ("BBBBB"); //iteratoresta apontando
> para uma posição válida
>
> map_test.erase ("BBBBB");// neste ponto oiteratordeixa de ser
> válido
>
> A questão é como faço para verificar se oiteratoriter_map_test é
> válido ? Pois qualquer operação que tento a partir do momento que o
> mesmo fica inválido causa uma excesão.
>
> Obrigado a todos.
Felipe Magno de Almeida
>
> Dei mais uma pesquisada sobre o assunto Iterator e finalmente descobri
> o motivo pelo qual minha indagação não pode ser atendida :
> Porque não há como testar/saber se um iterator é válido.
Foi o que a lista afirmou desde o inicio.
> Na verdade é muito simples, a partir do momento que um determinado
> ítem, que está sendo referenciado por um iterator qualquer, for
> deletado o iterator passa a apontar para uma área inválida.
Este é o comportamento de uma implementação comum, e normalmente
a mais rápida.
[snip]
> Por isto deve-se tomar muito cuidado com o uso de Iterator's,
> inclusive encontrei muitas recomendações de que seu uso deve ser o
> mais restrito possível.
Discordo veementemente. Como você pretende iterar sobre uma lista
sem usar iteradores?
Acredito que você está encarando o problema de forma errada, e por
isto está tendo problemas com iteradores.
[snip]
--
Felipe Magno de Almeida
lsalamon
minha implementação já está funcionando e muito bem, que tal 1.000.000
milhão de execuções dia, em 5 abr, 14:56, e meu interesse era o de
questionar sobre se existiria uma forma de testar se um Iterator é
válido ou não.
Apenas queria entender se isto poderia ser feito e claro, entender o
motivo de tal comportamento, e não apenas : Não é possível.
Não sou um acadêmico nem muito menos um doutor em todas as áreas do
assunto, mas para um bom programador em C, entender de ponteiros é o
básico, por isto minha analogia e obviamente o correspondente efeito.
Assunto esgotado.
Obrigado.
On 2 maio, 23:28, "Felipe Magno de Almeida"
<felipe.m.alme...@gmail.com> wrote:
> 2008/5/2 lsalamon <lsala...@gmail.com>:
Felipe Magno de Almeida
>
> A lista deve lembrar ("qual será sua cara?"),
Nao entendi o quote "qual será sua cara?".
> que eu já havia dito que
> minha implementação já está funcionando e muito bem,
Posso ter me enganado, mas pela thread entendi que você estava
recebendo exceções ao usar um interador inválido.
> que tal 1.000.000
> milhão de execuções dia, em 5 abr, 14:56,
Um milhão de milhões?
> e meu interesse era o de
> questionar sobre se existiria uma forma de testar se um Iterator é
> válido ou não.
>
> Apenas queria entender se isto poderia ser feito e claro, entender o
> motivo de tal comportamento, e não apenas : Não é possível.
Quando se fala em C++, presume-se o C++ padrão. E em C++ padrão
é dificil discutir implementação já que o padrão não obriga uma
implementação específica.
Também não percebi nenhuma pergunta sobre as razões do mesmo
nao ser garantido pelo padrão, apenas constatações de como um código
que invocava comportamento indefinido estava se comportando e a partir
deste comportamento circundar a inabilidade deste teste.
> Não sou um acadêmico nem muito menos um doutor em todas as áreas do
> assunto, mas para um bom programador em C, entender de ponteiros é o
> básico, por isto minha analogia e obviamente o correspondente efeito.
Sim. Mas não acredito que contestei nada disto. Só afirmei que discordo
das recomendações que recebeste sobre restringir o uso de iteradores.
Esta é, IMHO, uma recomendação muito ruim.
> Assunto esgotado.
Ok.
> Obrigado.
Rodrigo Strauss
(http://www.sgi.com/tech/stl/table_of_contents.html) diz que operações
invalidam ou não os iterators. Veja a referência de cada container.
Rodrigo Strauss
2008/5/2 lsalamon <lsal...@gmail.com>:
Blabos de Blebe
thread-safe baseadas em instruções atômicas do processador.
Novamente, as diferenças entre cientistas e engenheiros...
Boa pergunta!!!
2008/5/3 Rodrigo Strauss <rod...@1bit.com.br>: