Как лучше всего представить короткую битовую строку?

Я хочу представить строку длиной до 120 бит, и скорость имеет решающее значение. Мне нужно иметь возможность построить битовую строку с помощью повторяющихся операций snoc, а затем использовать ее с помощью повторяющихся операций uncons. Одна идея состоит в том, чтобы украсть реализацию Word128 из data-dword и использовать что-то вроде этого для сборки:

empty = 1
snoc xs x = (xs `shiftL` 1) .|. x

Но unconsing, кажется, становится немного уродливым, поскольку сначала нужно countLeadingZeros и сдвинуть влево, чтобы устранить их, прежде чем можно будет считать элементы, сдвигая и маскируя старшие биты.

Есть ли какой-то более приятный способ, который, по крайней мере, такой же быстрый, или какой-то более быстрый способ, который не слишком неприятный?

Контекст

Фил Раффвинд предложил версию at lens для Data.Map, но все реализации до сих пор существенно медленнее, чем наивная реализация lens, используемая в настоящее время, когда сравнение ключей дешево. Если бы я мог создать очень дешевое представление пути к записи при ее поиске, а затем очень эффективно использовать его с помощью специализированной версии insert или delete, тогда, возможно, я мог бы сделать это стоящим.


dictionary haskell bit-manipulation haskell-lens
person dfeuer    schedule 01.05.2016    source источник
comment
Может быть, превратить Word128 в кольцевой буфер? Просто сохраните индекс головы и хвоста вашей очереди.   -  person Daniel Wagner    schedule 02.05.2016
comment
@DanielWagner, это вариант. Для индекса требуется дополнительное слово, но это лучше. Кольцевой буфер или любая другая полная очередь — это немного больше, чем мне нужно, так как я делаю всю свою сессию, прежде чем начать несогласие.   -  person dfeuer    schedule 02.05.2016
comment
@dfeuer как насчет сохранения длины строки в дополнительных 8 битах? Вы можете прочитать эту длину перед snoc/uncons и записать ее после.   -  person erisco    schedule 02.05.2016
comment
@erisco, на самом деле это не поможет. Было бы лучше использовать отдельное слово, потому что распаковка и переупаковка этого байта все равно будут использовать его.   -  person dfeuer    schedule 02.05.2016
comment
@dfeuer, возможно, он распакован и сохранен в регистре, а не в кеше или основной памяти, что было бы выигрышем (меньший объем памяти позволяет вам поместить больше в строки кеша, если данные непрерывны). Если производительность настолько критична, возможно, стоит выяснить это.   -  person erisco    schedule 02.05.2016
comment
@erisco, хорошая мысль. Производительность критически важна. Является ли миссия критической — это совсем другой вопрос. ;-)   -  person dfeuer    schedule 02.05.2016
comment
Я вполне уверен, что countLeadingZeros будет самым быстрым, просто обязательно используйте unsafeShift и избегайте testBit и setBit (вместо этого переосуществите использование небезопасных сдвигов).   -  person András Kovács    schedule 02.05.2016
comment
@ AndrásKovács, могу я спросить, почему вы этого ожидаете? Я спрашиваю, потому что это доступно только в GHC ›= 7.10.   -  person dfeuer    schedule 02.05.2016
comment
@dfeuer Я отказываюсь от своего комментария, потому что решение Чи кажется таким же быстрым, как clz.   -  person András Kovács    schedule 03.05.2016
comment
@AndrásKovács AndrásKovács, мои тесты показывают, что ctz быстрее для uncons с двумя словами, но, конечно, также возможно, что виноват мой код. Работать с двумя словами больно. Я не уверен, что есть хороший способ справиться с переносчиками.   -  person dfeuer    schedule 03.05.2016

Ответы (1)


arrow_upward
2
arrow_downward

Я не уверен, подходит ли это. Я боюсь, что я повторно реализую countLeadingZeros в той или иной форме...

В любом случае, идея состоит в том, чтобы перехватывать биты слева, сдвигая вправо. Затем мы можем «подсчитать» конечные нули x, используя x-1 и XOR. Результатом «счета» является маска «00..01..11», которая, грубо говоря, является унарным представлением завершающих нулей. Мы не конвертируем это унарное в бинарное, так как нам это не нужно: с некоторой работой на уровне битов мы можем расконсервировать.

Далее следует непроверенный и непроверенный код.

import Data.Word
import Data.Bits
import Text.Printf

type T = Word64     -- can be adapted to any WordN

-- for pretty printing
pr :: T -> String
pr x = printf "%064b\n" x

empty :: T
empty = shiftL 1 63

snoc :: T -> T -> T
snoc x xs = shiftR xs 1 .|. (shiftL x 63)

-- returns (head, tail)
-- head is not normalized (0 or 1), only (0 or /=0)
uncons :: T -> (T, T)
uncons xs = 
   let -- example
       -- 0101001100000000000   xs  
       y = (xs `xor` (xs - 1))
       -- 0000000111111111111   y
       z = shiftR y 1 + 1
       -- 0000000100000000000   z
       z' = shiftL z 1
       -- 0000001000000000000   z'
   in (xs .&. z' , (xs .&. complement z) .|. z' )
person chi    schedule 01.05.2016
comment
Это действительно работает и по-своему довольно элегантно. К сожалению, кажется, что unconsing довольно медленный, по крайней мере, с реализациями, которые я придумал для двойных слов для соответствующих операций. Думаю, дальше я попробую одну из идей индексации.... - person dfeuer; 03.05.2016
comment
Я нашел где-то в Интернете, что вы можете перейти прямо к z = xs .&. (- xs). По совету Эдварда Кметта я решил попробовать использовать этот вариант из 1 слова с проверкой размера Map, чтобы отступить. К сожалению, кажется, что проблем с проверкой размера достаточно или почти достаточно, чтобы свести на нет время, сэкономленное за счет использования очереди из одного слова. Так что я думаю, что буду придерживаться двух слов countTrailingZeros вместо Data.Map. В очередной раз благодарим за помощь. - person dfeuer; 12.05.2016