Clojure 视频数据性能问题

Question

我正在编写一些代码来生成和处理大量视频数据。起初我只想使用随机数据。

我的技术是将像素视为 R、G、B、A 整数值的映射，将视频帧视为这些像素映射的向量，并将跨时间的视频视为这些向量的向量像素图。我编写了三个函数，可以可靠地执行此操作，但在缩放它们时遇到性能问题。

(defn generateFrameOfRandomVideoData
  "Generates a frame of video data which is a vector of maps of pixel values."
  [num-pixels-in-frame]
  (loop [num-pixels-in-frame num-pixels-in-frame
     pixels-added 0
     frame '[]]
(if (> num-pixels-in-frame pixels-added)
 (recur num-pixels-in-frame
        (inc pixels-added) 
        (conj frame (assoc '{} 
                           :r (rand-int 256)
                           :g (rand-int 256)
                           :b (rand-int 256)
                           :a (rand-int 256))))
 frame)))

(defn generateRandomVideoData
   "Generates a vector of frames of video data."
   [number-of-frames frame-height frame-width]
   (loop [number-of-frames number-of-frames
     frame-height frame-height
     frame-width frame-width
     frames '[]]
(if (> number-of-frames (count frames))
 (recur number-of-frames
        frame-height
        frame-width
        (conj frames (generateFrameOfRandomVideoData (* frame-height frame-width))))
 frames)))

 (defn generateRandomizedVideo
 "Generates video data based on the specified parameters."
 [number-of-frames frame-height frame-width]
    (assoc '{} 
     :number-of-frames number-of-frames
     :frame-height frame-height
     :frame-width frame-width
     :frames (generateRandomVideoData number-of-frames frame-height frame-width)))

调用此函数可生成 60 帧 1920X1080p 视频:

(generateRandomizedVideo 60 1920 1080)

当我运行此调用来生成 10 帧的 1920X1080p 视频时，算法很快完成。当我调用它来生成 60 帧视频时，它陷入困境，无法完成，并生成大量内存。我发现它占用了 16GB 的内存。

这对我来说没有任何意义。我的算法是O(帧数*(帧高*帧宽))。帧数为 O(n)，(帧的高度 * 帧的宽度恒定为 O(高度 * 宽度)。这些参数解析为 O(n)。

现在我已经说服了自己，也希望你相信我的算法并不简单，我想我有一些连贯的问题:

1. Clojure 中的整数占用多少位内存？我似乎无法在任何地方找到此信息。

2. 存储绑定(bind)到映射键的整数会导致什么样的开销？就内存而言，是否比将它们保存在向量中更昂贵？

3. 为什么算法在处理大量帧时会在时间和内存方面陷入困境？ Clojure 到底在做什么，占用了这么多内存？

谢谢!

Answer 1

How much memory does an integer in Clojure take up in bits?

16字节，根据clj-memory-meter :

(mem/measure (rand-int 256))
=> "16 B"

仅使用 4 个字节来表示 32 位整数值，但 Clojure 中的 java.lang.Integer 与 Java 中相同，并且还有额外的内容每个java.lang.Object的存储“开销”:

(type (rand-int 256))
 => java.lang.Integer

What kind of overhead does storing Integers bound to map keys cause? Is it costlier in terms of memory than just keeping them in a vector?

是的，在这种情况下几乎是两倍:

(mem/measure [(rand-int 256) (rand-int 256) (rand-int 256) (rand-int 256)])
=> "320 B"
(mem/measure {:r (rand-int 256)
              :g (rand-int 256)
              :b (rand-int 256)
              :a (rand-int 256)})
=> "544 B"

每一帧都会很大:

(mem/measure
  (into [] (repeatedly (* 1920 1080)
                       (fn [] {:r (rand-int 256)
                               :g (rand-int 256)
                               :b (rand-int 256)
                               :a (rand-int 256)}))))
 => "232.2 MB"

Why is the algorithm bogging down in terms of time and memory for large numbers of frames? What is Clojure doing to hog so much memory?

如果每个 1920x1080 帧约为 232 MB，那么每 4 帧约为 1 GB，那么每个像素存储一个 HashMap 将会很快增加。我不认为这是 Clojure 特有的——对于任何语言来说，这都是一个昂贵的存储方案。我会考虑以下几点:

• 更有效地存储各个像素值，例如将每个像素表示为打包成单个 32 位整数的四个无符号字节。当您拥有这么多数据点且全部位于同一结构中时，开放 HashMap 可能是空间效率最低的结构之一。

  由于您的 map 形状已明确定义，因此您可以使用记录来节省空间并具有类似 map 的语义:

  (defrecord Pixel [r g b a])
  (mem/measure (->Pixel (rand-int 256)
                        (rand-int 256)
                        (rand-int 256)
                        (rand-int 256)))
  => "112 B" ;; similar deftype is 96 B
  

  四个原始整数数组仅比单个 Integer 对象稍大:

  (mem/measure (int-array (range 4)))
  => "32 B"
  

  相似的向量大 10 倍:

  (mem/measure [(int 0) (int 1) (int 2) (int 3)])
  => "320 B"
  

  您可以尝试字节数组，但 JVM 没有无符号字节原语:

  (mem/measure (byte-array 4))
  => "24 B"
  

• 在每个像素和帧都conj到现有向量的情况下，会发生很多不可变的数据结构变化，而这并不是“免费”的使用 Clojure 的持久数据结构。更有效的方法是使用 transients ，但是……

• 您需要将所有这些帧存储在内存中吗？如果没有，您可以懒惰地流式传输这些内容，而无需将它们全部保留。如果您必须将它们构建到一个大型的、已实现的集合中，也许可以使用 transient 、JVM 数组等。

  (defn gen-frame [num-pixels]
    (repeatedly num-pixels
      #(->Pixel (rand-int 256) (rand-int 256) (rand-int 256) (rand-int 256))))    
  (defn frame-op [frame] ;; not very interesting for random pixels
    (let [num-pixels (count frame)
          avg #(double (/ (apply + (map % frame)) num-pixels))]
      (->Pixel (avg :r) (avg :g) (avg :b) (avg :a))))    
  (time
    (->> (repeatedly #(gen-frame (* 1920 1080)))
         (map frame-op)
         (take 60)
         (doall)))
  "Elapsed time: 240527.803662 msecs"
  =>
  (#sandbox.core.Pixel{:r 127.4540152391975, :g 127.4542722800926, :b 127.3754962384259, :a 127.4886294367284}
   #sandbox.core.Pixel{:r 127.4727488425926, :g 127.4447955246914, :b 127.4472164351852, :a 127.4626080246914}
   ...
  

  此示例延迟分析无限序列的每一帧并获取前 60 个结果；分析的帧/像素数据在运行时会被垃圾收集，因此不会耗尽内存(但 GC 会很忙)。

These arguments resolve to O(n).

有时大常数很重要!