Класс

← →
Igorek (2002-12-18 14:07) [0]

Подскажите реализацию такого класса.
Как держать набор битов понятно - набор байтов.
А как сделать быструю запись/считывание определенного бита?
Можно конечно сделать свойство Bits[Integer], но не будет ли это проиграш в производительности? Наверно будет, так как же иначе?

← →
Digitman (2002-12-18 14:21) [1]

Если заботит производительность кода, интенсивно использующего такое св-во, то следует, imho, реализовать методы SetBits(), GetBits() с использованием инструкций bt, bts, btr в ASM-блоках в телах каждого из методов.
Эти инструкции (в подавляющем большинстве случаев) наиболее эффективны для организации побитового обращения к непрерывному массиву произвольного размера

← →
MBo (2002-12-18 14:28) [2]

TBits по производительности не устроит?

← →
Skier (2002-12-18 14:31) [3]

>Igorek
большой набор битов ? (сколько) ?

← →
Igorek (2002-12-18 14:33) [4]

> Digitman © (18.12.02 14:21)

Да, но кроме реализации методов чтения/записи их же надо вызывать с целочисленным параметром. Вот здесь то и будет узкое место.
В асме я не силен, не могли бы Вы написать эти два метода.
Пусть будет так:
TBitMask = class private FBits: array of Byte; protected procedure SetBits(Index: Integer; Value: Boolean); function GetBits(Index: Integer): Boolean; public property BitCount: Integer ... property Bits[Index: Integer]: Boolean read GetBits write SetBits; end; procedure TBitMask.SetBits(Index: Integer; Value: Boolean); begin //insert code here plz end; function TBitMask.GetBits(Index: Integer): Boolean; begin //insert code here plz end;

← →
Igorek (2002-12-18 14:35) [5]

MBo © (18.12.02 14:28)
> TBits по производительности не устроит?

Спасибо большое! Вопрос закрыт. :-)

← →
Digitman (2002-12-18 14:57) [6]

TBitMask = class private FBits: Pointer; // !!!!!!!!!!!!!!!!!!!!!!!!!!! protected procedure SetBits(Index: Integer; Value: Boolean); function GetBits(Index: Integer): Boolean; public property BitCount: Integer ... property Bits[Index: Integer]: Boolean read GetBits write SetBits; end; ... procedure TBitMask.SetBits(Index: Integer; Value: Boolean); asm mov eax, [eax].TBitMask.FBits test cl, cl jz @@clr_bit bts [eax], edx ret @@clr_bit: btr [eax], edx end; function TBitMask.GetBits(Index: Integer): Boolean; asm mov eax, [eax].TBitMask.FBits lahf mov al, ah and ax, 1 end;

каким образом ты инициализируешь указатель FBits - неважно.

важно лишь, чтобы в момент обращения к св-ву Bits[] он указывал на начальный адрес блока последовательных байт в памяти приложения (нужного тебе размера)

array of byte оч.нежелателен,
обращение к блоку памяти, явно выделенному/перераспределенному по GetMem/ReallocMem будет гораздо эффективней

← →
Igorek (2002-12-19 12:22) [7]

> Digitman © (18.12.02 14:57)

В VCL класс TBits я думаю грамотно написан. Там кстати и проверка ошибок есть на асме. Но все равно спасибо.

← →
Digitman (2002-12-19 12:32) [8]

> Igorek

Ты просто посмотри дебагером в окне CPU (при выполнении интересующих тебя методов) и убедись воочию, есть там упомянутые инструкции или нет. Если есть, то TBits, наверно, не самый худший вариант решения. По кр.мере, этот "узкий" момент там, вероятно, выполнен грамотно. Я просто не в курсе, не пользовал этот класс

← →
Digitman (2002-12-19 12:35) [9]

Не парься)
Я уже посмотрел в исходники TBits.
Вполне нормально сделано, стоит рассмотреть в кач-ве приемлемого решения

← →
А (2002-12-20 03:21) [10]

кстати, "Ну Очень Интересная Тема".
Хочу сразу сказать, что очень люблю "Set of". Но "Set" ограничен числом 256 :(((
По поводу выше упомянутого, и выше сказанного "Digitman""ом - установка и снятие соответсвующего бита - понятна. Но (вот тут теперь вопрос). А есть ли столь же "быстрые" алгоритмы неких других операций над "множествами битов", например "объединение" или "пересечение"?

← →
Digitman (2002-12-20 08:30) [11]

> есть ли столь же "быстрые" алгоритмы неких других операций
> над "множествами битов", например "объединение" или "пересечение"?

Алгоритмы, наверно, есть. Но подобные маш.инструкции мне неизвестны.
Скажу лишь, что любой сколь угодно сложный алгоритм работы с множествами можно оптимизировать с применением все тех же инструкций bt, btr, btc и пр.

← →
vvolkov (2002-12-20 11:24) [12]

> (вот тут теперь вопрос). А есть ли столь же "быстрые" алгоритмы
> неких других операций над "множествами битов", например
> "объединение" или "пересечение"?

Объединением двух множеств заданных в виде массивов байт будет последовательное выполнение операции OR над элементами этих массивов. Пересечение соотвествено AND.

← →
Угу (2002-12-21 03:57) [13]

попробую придумать сии алгоритмы или найти. А суть моего вопроса А (20.12.02 03:21)
была в том, что в своей программе ранее использовал Set of и был вполне доволен жизнью, пока эта самая жизнь не "ударила мне ключом по голове", а именно не создала ситуацию, где количество элементов множества стало превышать 256! Выход то, конечно нашел, но на паскале, а ведь на ассемблере может быть я не потерял бы эффективнось "множеств"?

← →
А (2002-12-21 04:12) [14]

кстати еще один вопрос к Digitman.
Вы - один из самых опытных по части ассемблера. Может подскажете пособия по нему, не важно бумажные или электронные. И к тому же те, которые учитывают наличие нескольких фирм производителей современных процессоров.

← →
Anatoly Podgoretsky (2002-12-21 12:37) [15]

Надо учитывать, что для хранения 8 бит подряд, требуется один бай и для реализации Set Of Integer потребуется 128 мегабайт.
А с алгоритмами проблем нет Основаны на простых операциях div 8, mod 8 (компилятор заменит на сдвиги) и дальше OR/AND/NOT
писать конечно можно на ассемблере, но и Дельфи комплятор создаст такой же эффективный код.
Необзательно реализовывать все опереции с множеством, для начала достаточно + - IN

← →
Угу (2002-12-22 03:05) [16]

Для начала, конечно же "+ - IN" - достаточно. Но эти операции действительно ну очень простые. Это "начало" уже давно пройдено. Может я не прав, и "Дельфи комплятор создаст такой же эффективный код", но может Вы, Анатолий, дадите ссылку на (хотя бы на) некое пособие, в котором есть перечень инструкций для современных процессоров с, хотя бы, краткими комментариями к ним типа "размер в байтах", "кол-во маш. тактов". Ну как у Дао было ранее (наверняка Вы помните его книжку о процессоре 8086).

← →
Угу (2002-12-22 03:13) [17]

← →
Anatoly Podgoretsky (2002-12-22 10:32) [18]

Такая инструкция есть у Интела и не одна, кажется и АМД тоже отдает документацию

← →
Digitman (2002-12-22 13:07) [19]

>А

Оптимизировать работу с массивами-множествами, imho, можно конечно попытаться с применением и целочисленных packed-инструкций, таких как pand, pandn, por, pxor. Эти инструкции позволяют обрабатывать целочисленные операнды размером в QWORD (64-бит) практически за то же число тактов, что и их 32-разрядные прототипы (and, or, xor). Естественно, достичь максимальной производительности кода, выполняющего подобные инструкции, можно лишь тогда, когда src/dst-операнды выровнены в памяти по границе QWORD.
Плохо еще и то, что одним из операндов этих инструкций может выступать только mm-регистр, т.е. требуется еще 7-8 тактов на загрузку/выгрузку mm-регистрового операнда-результата в/из памяти.

Встроенный ассемблер Делфи, к сож., не распознает мнемоники этих инструкций (по кр.мере - Д5), но ради благой цели ничто не мешает попробовать построить OBJ-модуль (задействующий эти инструкции) в том же TASM"ме и затем подключить модуль директивой {$LINK}. Или же сгенерировать соотв.инструкции обычными db-директивами.

Все же, думается, в подавляющем большинстве случаев "овчинка выделки не стоит". Алгоритмы с использованием строковых инструкций загрузки/выгрузки дв.слов (lodsd, stosd) успешно конкурируют с инструкциями mmx-расширения

← →
Anatoly Podgoretsky (2002-12-22 13:12) [20]

Начиная с Д7 можно в полной мере

← →
Спасибо (2002-12-23 03:20) [21]

Анатолий и Digitman.
Учту Ваши советы.
Но КАК хороша была ранее жизнь! Погода была замечательная, цены - низкие, солнце - теплое, люди - добрые. Да к тому же числа укладывались в байты. :-0)
Но на Д7 пока переходить не готов (морально).

С почтением "УГУ" и "А". (И иже с ними).

Класс Найти похожие ветки