Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2003.01.06;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]

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


 
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 пока переходить не готов (морально).

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



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2003.01.06;
Скачать: [xml.tar.bz2];

Наверх





Память: 0.63 MB
Время: 0.049 c
1-15118
^Sanya
2002-12-21 16:30
2003.01.06
Помогите, просто необходимо...


14-15250
Axis_of_Evil
2002-12-16 11:17
2003.01.06
А есть ли среди местных геймеры ?


1-15154
gerd
2002-12-23 17:52
2003.01.06
Как связать Word документ с моим приложением?


1-15087
Костяну
2002-12-22 12:38
2003.01.06
инженерная дорожка


1-15035
adolf_99
2002-12-24 19:28
2003.01.06
Помогите





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский