Estoy escribiendo un código para generar y procesar grandes cantidades de datos de video. Al principio, solo pretendo trabajar con datos aleatorios.

Mi técnica es tratar un píxel como un mapa de valores enteros R, G, B, A, tratar un fotograma de video como un vector de estos mapas de píxeles y tratar el video a lo largo del tiempo como un vector de estos vectores de mapas de píxeles. . He escrito tres funciones que hacen esto de manera confiable, pero tengo problemas de rendimiento cuando se escalan.

(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)))

Llámelo para usar las funciones para generar 60 cuadros de video de 1920X1080p:

(generateRandomizedVideo 60 1920 1080)

Cuando ejecuto esta llamada para generar 10 cuadros por valor de video de 1920X1080p, el algoritmo se completa con bastante rapidez. Cuando lo llamo para producir 60 cuadros de video, se atasca, no se completa y genera enormes cantidades de memoria. Vi que ocupaba 16 GB de memoria.

Esto realmente no tiene ningún sentido para mí. Mi algoritmo es O (número de fotogramas * (altura del fotograma * ancho del fotograma)). El número de fotogramas es O (n) y (altura del fotograma * ancho del fotograma es constante en O (alto * ancho). Estos argumentos se resuelven en O (n).

Ahora que me he convencido a mí mismo y espero que a usted de que mi algoritmo no es simplemente intratable, creo que tengo algunas preguntas coherentes:

  1. ¿Cuánta memoria ocupa un número entero en Clojure en bits? Parece que no puedo encontrar esta información en ningún lado.

  2. ¿Qué tipo de sobrecarga provoca el almacenamiento de enteros vinculados a claves de mapa? ¿Es más costoso en términos de memoria que simplemente mantenerlos en un vector?

  3. ¿Por qué el algoritmo se atasca en términos de tiempo y memoria para un gran número de fotogramas? ¿Qué está haciendo Clojure para acaparar tanta memoria?

¡Gracias!

4
jared-nelsen 5 feb. 2019 a las 03:49

2 respuestas

La mejor respuesta

¿Cuánta memoria ocupa un número entero en Clojure en bits?

16 bytes, según clj-memory-meter:

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

Solo se utilizan 4 bytes para representar un valor entero de 32 bits, pero un java.lang.Integer en Clojure es el mismo que en Java, y hay una "sobrecarga" de almacenamiento adicional para cada {{X1} }:

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

¿Qué tipo de sobrecarga provoca el almacenamiento de enteros vinculados a claves de mapa? ¿Es más costoso en términos de memoria que simplemente mantenerlos en un vector?

Sí, casi el doble en este caso:

(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"

Cada cuadro será bastante grande:

(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"

¿Por qué el algoritmo se atasca en términos de tiempo y memoria para un gran número de fotogramas? ¿Qué está haciendo Clojure para acaparar tanta memoria?

Almacenar un mapa hash por píxel se sumará muy rápidamente, si cada cuadro de 1920 x 1080 es ~ 232 MB, eso es ~ 1 GB cada 4 cuadros. No creo que esto sea específico de Clojure; este es un esquema de almacenamiento costoso para cualquier idioma. Consideraría algunas cosas:

  • Almacene los valores de píxeles individuales de manera más eficiente, p. Ej. representar cada píxel como cuatro bytes sin firmar empaquetados en un solo entero de 32 bits. Un mapa hash abierto es probablemente una de las estructuras menos eficientes en espacio cuando tiene tantos puntos de datos, todos en la misma estructura.

    Dado que la forma de su mapa está bien definida, puede usar un registro para ahorrar espacio y tener una semántica similar a un mapa:

    (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
    

    Una matriz entera primitiva de cuatro es solo un poco más grande que un solo objeto Integer:

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

    Un vector similar es 10 veces más grande:

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

    Puede probar una matriz de bytes, pero JVM no tiene primitivas de bytes sin firmar :

    (mem/measure (byte-array 4))
    => "24 B"
    
  • Hay una gran cantidad de cambios de estructura de datos inmutables en los que cada píxel y fotograma se coloca conj en un vector existente, y eso no viene "gratis" con las estructuras de datos persistentes de Clojure. Una forma más eficiente de hacer esto es usar transitorios, pero ...

  • ¿Necesita almacenar todos estos marcos en la memoria? De lo contrario, puede transmitirlos de forma perezosa sin tenerlos todos. Si tiene que construirlos en una colección grande y realizada, tal vez use transitorios, matrices JVM, etc.

    (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}
     ...
    

    Este ejemplo analiza perezosamente cada fotograma de una secuencia infinita y toma los primeros 60 resultados; los datos de fotogramas / píxeles analizados se recolectan basura mientras se ejecuta, por lo que no se quedará sin memoria (pero el GC estará ocupado).

Estos argumentos se resuelven en O (n).

¡Las grandes constantes importan, a veces!

7
Taylor Wood 5 feb. 2019 a las 15:58

Si necesita una mayor aceleración de lo que puede obtener de la respuesta de @Taylor Wood, considere comprimir aún más su almacenamiento.

Si solo presiona 99, Clojure lo almacenará como java.lang.Long, ocupando 64 bytes por número. El uso de java.lang.Integer lo reducirá a la mitad, ocupando 32 bytes por número.

¡Pero tenemos más margen de optimización! Generas números entre 0 y 255, lo que significa que necesitas log2(256) = 8 bits para el almacenamiento por número. ¡Entonces podríamos ajustar los tres valores RGB en un solo java.lang.Integer!

Empecé a continuación. Los créditos para este enfoque van a mikera / imagez. Si tiene ganas de modificar más, puede intentar evitar mi uso de rem y quot y, en su lugar, ir a jugar un poco. La memoria será la misma, pero el uso de la CPU disminuirá.

(defn encodable? [i]
  (and (nat-int? i)
       (< i 256)))

(defn rgb->int
  "Store an RGB value in a single integer!"
  [[r g b]]
  (do (assert (encodable-int? r))
      (assert (encodable-int? g))
      (assert (encodable-int? b)))
  (int
   (+ (* 256 256 r)
      (* 256 g)
      b)))

(defn int->rbg [i]
  [(rem (quot i (* 256 256)) 256)
   (rem (quot i 256) 256)
   (rem i 256)])

;; Let's try to store 99, 101, 255!

(def c [99 101 255])

(rgb->int c)
;; => 6514175

(type (rgb->int c))
;; => java.lang.Integer

(-> c rgb->int int->rbg)
;; => [99 101 255]
0
Teodor 6 feb. 2019 a las 21:11