haskell 如何将文本转换为矢量而不需要额外的分配

0tdrvxhp 于 2023-11-18 发布在其他

关注(0)|答案(1)|浏览(100)

我有一个关于将Text转换为Data.Vector.Unboxed.Vector的最有效方法的问题。我一直在使用像这样的weigh基准测试工具进行测试，我看到了很多无关的分配：

{-# LANGUAGE BangPatterns #-}
module Main (main) where

import Control.Monad
import Data.String.Interpolate
import Data.Text as T
import qualified Data.Vector.Unboxed as VU
import Weigh

testFunc :: Int -> Text -> Weigh ()
testFunc inputSize text = wgroup [i|#{inputSize} characters|] $ do
  func' "VU_fromList" VU.fromList (T.unpack text)
  func' "VU_fromListN" (\t -> VU.fromListN (T.length t) (T.unpack t)) text

main :: IO ()
main = mainWith $
  forM_ [10, 100, 1000, 10000, 100000] $ \n -> do
    let !text = T.replicate n "0"
    testFunc n text

字符串
在我的结果中，将10个字符转换为一个向量需要256字节的分配。转换10万个字符需要1 M字节。我认为这是因为我使用T.unpack，编译器在内存中创建了中间列表元素。有没有一种方法可以只分配一个所需大小的向量，并在复制内容的同时遍历文本？
也许我可以使用Data.Vector.create函数吗？但是我找不到一种方法来遍历Text的monadically。
完整的基准测试文件和结果在这里：
https://gist.github.com/thomasjm/7c2bd4f25ba4a75e90b898a902725ead
编辑：哦，我忘了说有一种方法是有效的，但它是二次时间。它是这样的：

generateMethod :: Text -> VU.Vector Char
generateMethod t = VU.generate (T.length t) (T.index t)

型
这个方法使用了大约4x个字节，其中x是字符数，正如您对UTF-8的期望。

haskell

来源：https://stackoverflow.com/questions/77385819/how-to-convert-text-to-vector-without-extraneous-allocations

1条答案

按热度按时间

vvppvyoh1#

主要有两个问题：

我们需要遍历文本，但是文本API没有提供直接使用用例的函数。
例如，T.uncons不起作用，maybe和tuple在大多数情况下可以被优化掉，但剩余文本的分配通常不会被优化掉（尽管VU.unfoldr似乎确实发生了这种情况）。
我们需要构建向量，但向量API没有提供一次性分配整个向量的函数。
所有的函数，甚至VU.unfoldrN似乎都在这个过程中增加了向量。我认为这是因为这种实现策略适合于融合，但这确实意味着你要牺牲一点效率。

为了解决1，我选择了直接使用内部流表示，这确实允许您编写有效的遍历。
为了解决问题2，我选择了手动创建一个可变向量，你也已经考虑过了。

...
import Data.Text.Internal.Fusion
import qualified Data.Vector.Unboxed.Mutable as M

streamCreateMethod :: Text -> VU.Vector Char
streamCreateMethod t =
  case stream t of
    Stream step s0 _ -> VU.create $ do
      m <- M.new (T.length t)
      let 
        go s i =
          case step s of
            Done -> pure ()
            Skip s' -> go s' i
            Yield x s' -> do
              M.write m i x
              go s' (i + 1)
      go s0 0
      pure m

字符串
性能指标评测结果（使用tasty-bench和+RTS -T，这是我首选的性能指标评测方法）：

10 characters:     OK
    32.8 ns ± 2.6 ns, 111 B  allocated,   0 B  copied, 6.0 MB peak memory
  100 characters:    OK
    228  ns ±  21 ns, 471 B  allocated,   0 B  copied, 6.0 MB peak memory
  1000 characters:   OK
    2.15 μs ± 179 ns, 3.9 KB allocated,   0 B  copied,  10 MB peak memory
  10000 characters:  OK
    21.1 μs ± 1.5 μs,  39 KB allocated,   2 B  copied,  10 MB peak memory
  100000 characters: OK
    211  μs ±  14 μs, 386 KB allocated,  21 B  copied,  12 MB peak memory

型
(for内存使用情况，请查看分配的数量，而不是整个程序（包括多次迭代）运行过程中的峰值。）
Jon Purdy提出了使用encodeUtf32LE和unsafeFromForeignPtr的解决方案，所以我也尝试了一下：

encodeMethod :: Text -> VS.Vector Char
encodeMethod t = 
  case encodeUtf32LE t of
    BS ptr len -> 
      runST $ VS.unsafeFreeze $ 
        VSM.unsafeFromForeignPtr0 (castForeignPtr ptr) (len `quot` 4)))

型
但是，这一点的表现要差得多：

10 characters:     OK
    281  ns ±  24 ns, 3.3 KB allocated,   0 B  copied, 6.0 MB peak memory
  100 characters:    OK
    2.32 μs ± 181 ns,  31 KB allocated,   2 B  copied, 6.0 MB peak memory
  1000 characters:   OK
    22.3 μs ± 1.8 μs, 302 KB allocated,  20 B  copied, 6.0 MB peak memory
  10000 characters:  OK
    221  μs ±  11 μs, 3.0 MB allocated, 212 B  copied, 6.0 MB peak memory
  100000 characters: OK
    2.31 ms ± 169 μs,  30 MB allocated,  85 KB copied, 7.0 MB peak memory

型
现在我已经创建了一个对text库的pull请求，它将foldlM添加到了公共API：
https://github.com/haskell/text/pull/543

赞(0）回复(0）举报 2023-11-18

我来回答

haskell 如何将文本转换为矢量而不需要额外的分配

1条答案

相关问题

热门标签

最新问答