Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Пул объектов


Автор: SABROG 27.3.2010, 22:06
Код

/*!
    Returns a QMutex from the pool. QMutexPool uses the value \a address
    to determine which mutex is returned from the pool.
*/
QMutex *QMutexPool::get(const void *address)
{
    Q_ASSERT_X(address != 0, "QMutexPool::get()", "'address' argument cannot be zero");
    int index = int((quintptr(address) >> (sizeof(address) >> 1)) % mutexes.count());

    if (!mutexes[index]) {
        // mutex not created, create one
        QMutex *newMutex = new QMutex(recursionMode);
        if (!mutexes[index].testAndSetOrdered(0, newMutex))
            delete newMutex;
    }

    return mutexes[index];
} 


В Qt каждый созданный QObject добавляет в конструкторе мутекс на адрес экземпляра класса в общий пул мутексов. Я нигде не нашел, чтобы мутекс удалялся, даже когда память под объект уже давно освобождена. Пул мутексов мочится целиком только когда последний QObject в программе уничтожен.

Заинтересовала эта строчка формирования индекса:

Код

    int index = int((quintptr(address) >> (sizeof(address) >> 1)) % mutexes.count());


Если предположить, что объекты размеров в байт будут располагаться по адресам 100,101,102:

Код

100 = 100 / 4 = 25 % 3 = 1
101 = 101 / 4 = 25 % 3 = 1
102 = 102 / 4 = 25 % 3 = 1


То на все эти адреса будет один и тот же мутекс? Теперь увеличим дистанцию на 32 бита, возможно мутексы не умеют работать с данными меньше 4х байт:
Код

100 = 100 / 4 = 25 % 3 = 1
104 = 104 / 4 = 26 % 3 = 2
108 = 108 / 4 = 27 % 3 = 0


Тут каждый объект получил по своему личному мутексу. А теперь увеличим размер указателя до 8 байт (вообще указатель void* может иметь разные размеры на одной и той же машине?):

Код

100 = 100 / 16 = 6 % 3 = 0
108 = 108 / 16 = 6 % 3 = 0
116 = 116 / 16 = 7 % 3 = 1
124 = 124 / 16 = 7 % 3 = 1


То есть на 2 объекта по 1 общему мутексу. Я чего-то не понимаю или залочка одного мутекса для одного объекта может блокировать работу другого объекта? Что если объекты находятся вообще в разных потоках и работают асинхронно? Ну и соответственно если я создам пару миллионов объектов, то из-за операции взятия остатка на многие из них будут снова общие мутексы.

Означает ли это, что каждый раз, когда я в слоте пытаюсь узнать кто послал сигнал через метод sender():

Код

QObject *QObject::sender() const
{
    Q_D(const QObject);

    QMutexLocker locker(signalSlotLock(this));
    if (!d->currentSender)
        return 0;

    // Return 0 if d->currentSender isn't in d->senders
    bool found = false;
    for (QObjectPrivate::Connection *c = d->senders; c && !found; c = c->next)
        found = (c->sender == d->currentSender->sender);
    if (!found)
        return 0;
    return d->currentSender->sender;
} 


То вот этот "друг"

Код

QMutexLocker locker(signalSlotLock(this));


Может заблокировать параллельно еще какой-нибудь случайный QObject, например QTcpSocket, который пытается принять в отдельном потоке клиента? Потому, что:

Код

static QMutex *signalSlotLock(const QObject *o)
{
    if (!signalSlotMutexes) {
        QMutexPool *mp = new QMutexPool;
        if (!signalSlotMutexes.testAndSetOrdered(0, mp)) {
            delete mp;
        }
    }
    return signalSlotMutexes->get(o);
} 


Может получить общий мутекс? Или у меня с математикой что-то плохо?

Автор: borisbn 28.3.2010, 22:31
а точно signalSlotMutexes является QMutexPool * ?

может быть
Цитата(SABROG @  27.3.2010,  22:06 Найти цитируемый пост)

Код

return signalSlotMutexes->get(o);


не является вызовом 
Цитата(SABROG @  27.3.2010,  22:06 Найти цитируемый пост)

Код

QMutex *QMutexPool::get(const void *address)

Автор: SABROG 28.3.2010, 22:45
Цитата(borisbn @  28.3.2010,  22:31 Найти цитируемый пост)
а точно signalSlotMutexes является QMutexPool * ?

Он так объявлен в qobject.cpp:

Код

static QBasicAtomicPointer<QMutexPool> signalSlotMutexes = Q_BASIC_ATOMIC_INITIALIZER(0);


То есть это своего рода "умный указатель" QBasicAtomicPointer.

Автор: borisbn 28.3.2010, 22:57
SABROG, да, уже посмотрел. получается, что действительно вызов sender() может заблокировать вызов sender() из другого объекта. заметь, блокируется не объект, а вызов sender(), и не более того

P.S. Может стоит перенести тему в "С/С++: Кроссплатформенное программирование, QT/Gtk+/wxWidgets" ?

Автор: SABROG 28.3.2010, 23:32
Цитата(borisbn @  28.3.2010,  22:57 Найти цитируемый пост)
может заблокировать вызов sender()

sender() я взял как наиболее часто употребимый вариант, но там и другие методы есть, которые вызывают блокировку.

Цитата(borisbn @  28.3.2010,  22:57 Найти цитируемый пост)
Может стоит перенести тему в "С/С++: Кроссплатформенное программирование, QT/Gtk+/wxWidgets"

Речь не совсем о Qt, меня интересует верность рассчетов индекса от адреса объекта. Задача скорее математическая. Либо я чего-то не правильно посчитал, либо это так и есть. Может быть просто кто-то видел подобный алгоритм поиска объекта в массиве по адресу объекта в других проектах?

Автор: borisbn 28.3.2010, 23:59
Цитата(SABROG @  28.3.2010,  23:32 Найти цитируемый пост)
Может быть просто кто-то видел подобный алгоритм поиска объекта в массиве по адресу объекта в других проектах

по-моему, это обычный hash (кстати, в более ранней версии Qt использовался как раз QHash, а не остаток от деления)
ну, а если быть совсем точным, то
Код

100 = 100 / 4 = 25 % 3 = 1
101 = 101 / 4 = 25 % 3 = 1
102 = 102 / 4 = 25 % 3 = 1

верно для 64-х битных указателей, т.к. для 32-х разрядной ОС
sizeof(address)  >> 1 = 2, т.е. должно быть
Код

100 = 100 / 2 = 50 % 3 = 2
101 = 101 / 2 = 50 % 3 = 2
102 = 102 / 2 = 50 % 3 = 2

Автор: SABROG 29.3.2010, 00:13
Цитата(borisbn @  28.3.2010,  23:59 Найти цитируемый пост)
т.е. должно быть

Обрати внимание, там сдвиг идет в 2 этапа:

Код

sizeof(address) >> 1


4 >> 1 эквивалентно: 4/2 = 2

Потом второй этап:

Код

quintptr(address) >> 2


То есть смещение уже зависит от размера указателя. А смещение на 2 эквивалентно делению на 4.

Вот таблица, чтобы понятней было:

Код

2,4,8,16,32,64,128,256,512,1024


Отсчет ведется с 1 до 10. Первая цифра смещение на 1 == делению на 2, смещение на 2 == делению на 4 и так далее.

В QHash не обнаружил подобного кода.
---
Сейчас погуглил, наткнулся на такой код:

Код

    virtual U_32 getKeyHashCode(void* key) const {
        // return hash of address bits
        return ((U_32)(((POINTER_SIZE_INT)key) >> sizeof(void*)));
    }


То есть правда в твоих словах есть. Остается понять откуда взялась вторая часть и почему хеш получается не уникальным.
---
При беглом прочтении нескольких статей про хэши сделал вывод, что коллизия обычное дело. Если она возникает, то обычно сравниваются уже значения, если они разные, то происходит rehash. В случае с Qt слежения за коллизиями я не увидел, так как сами адреса нигде не хранятся, вместо них хранятся данные, которые никак к адресам не привязаны. Воозможно еще проблема в том, что я взал маленькие значения адресов, может быть при каких-нибудь 0x00410000h я буду уже не так часто получать коллизии?

Автор: borisbn 29.3.2010, 07:06
SABROG, 
1. Про сдвиг значения указателя на 2 -я протупил
2. В старом, ещё trolltech'вском коде mutex получался через QHash от указателя
3. Значение самого указателя (100 или 410000h) не играет роли, т.к. они берут остаток от деления на количество mutex'ов.
Слежения за коллизиями я тоже не увидел, значит получается, что все функции, использующие QMutexPool могут блокировать друг друга

Автор: SABROG 29.3.2010, 08:51
Написал троллям, посмотрим чего они скажут.

Автор: SABROG 29.3.2010, 14:46
Thiago Maciera написал такой ответ и пометил багрепорт как invalid:

Цитата

The sizeof such objects is almost never 1. It's usually a multiple of sizeof(void*).


Говорит, что размер объекта почти никогда не бывает 1 байт и обычно составляет несколько размеров указателя void*. Раз несколько, то минимум 8 байт (по 4 байта на указатель). Но я оставил коммент, что даже в этом случае коллизии есть.
---
Цитата

Remember that object addresses will be kind of randomized by the allocator.
specially if they are living in different threads, there is very small likelyhood that the objects will have addresses that are that close anyway.

If you can provide a compilable testcase that shows any performance penalty because of those locks, you are welcome.

Notice that at least QObject::receivers and QObject::dumpObjectInfo() are not optimized for speed as they are debugging functions.


Хотят компилируемый пример с тормозами  smile То есть тот факт, что подобная проблема может выскочить их не волнует.
---
Кому интересно, за перепиской с троллями можно наблюдать http://bugreports.qt.nokia.com/browse/QTBUG-9461.

Выяснилась еще одна особенность. Максимальное количество мутексов - 131. Если при этом в программе 10 тысяч объектов, то на каждый мутекс может приходится 70-80 объектов. При 200 объектах это значение не так великов 1-5, но факт остается фактом, а возможность коллизии довольно большая.

P.S.: математический вопрос считаю решенным, тема перетекла в русло Qt, можно переместить в соответствующий раздел. Спасибо borisbn за подсказку с хэшами, плюс один.

Автор: borisbn 30.3.2010, 10:07
Цитата(SABROG @  29.3.2010,  14:46 Найти цитируемый пост)
If you can provide a compilable testcase that shows any performance penalty because of those locks, you are welcome

хитрые тролли  smile . Ведь может быть так, что у тебя или у меня на компьютере проблема возникнет, а у них - нет, потому что память разляжется по-другому и указатели не пересекутся
----------------------------------------
Vladislav, прочитал переписку. IMHO - очень дельное предложение сделать отдельный QMutexPool для каждого потока.
Буду следить за войной русского программиста с финскими кодерами smile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)