Xeno.DOM: Heap exhausted on a 5.6M file

[unhammer]

longlines.xml.zip
↑ through xeno-dom exhaust heap memory. I just put the file into the list in SpeedBigFiles.hs as
[ benchFile ["xeno-dom"] "6MB" "longlines.xml.bz2"
and got

benchmarking 6M/xeno-dom
xeno-speed-big-files-bench: Heap exhausted;
xeno-speed-big-files-bench: Current maximum heap size is 26843545600 bytes (25600 MB).

Strangely, only minor changes to the file (e.g. sed 's/x/xx/g – increasing the file size) will let it through with about 800M maxresident (as reported by /usr/bin/time). Inserting newlines after each > we also get 800M maxresident, but it doesn't seem to be related to the long lines, as almost any change to the file helps.

(Yes I should be using Xeno.SAX, but why does e.g. https://dumps.wikimedia.org/nowiki/20230520/nowiki-20230520-pages-articles-multistream-index.txt.bz2 at 11M go through fine with <400M maxresident and this one not? Even removing newlines, the wiki works fine. This feels like leakage.)

[ocramz]

@unhammer perhaps you could try this test with the latest master ? see #63

[unhammer]

The issue remains :(

[ocramz]

"fy fan". Ok this requires some deeper thinking.

[ocramz]

@unhammer anyway, it's at least reassuring that the latest patch doesn't change the memory behavior of the library (kudos @mitchellwrosen )

[unhammer]

For now I'm using this dumb intermediate module which is like 30% slower than Xeno.DOM but at least doesn't crash and lets me reuse my old code unchanged with just a change from Xeno.DOM to Xeno.DOMB:

{-# LANGUAGE OverloadedRecordDot #-}

module Xeno.DOMB where

import Prelude

import Data.ByteString (ByteString)
import qualified Xeno.SAX as X
import Xeno.Types (XenoException (..))


data Node = Node
    { name       :: ByteString
    , attributes :: [(ByteString, ByteString)]
    , children   :: [Node]
    } deriving Show


-- | Ignores text and CDATA
parse :: ByteString -> Either XenoException Node
parse bs = case X.fold onOpenTag onAttr onEndOpenTag onText onCloseTag onCDATA [] bs of
    Left e       -> Left e
    Right [root] -> Right root
    Right _      -> Left XenoExpectRootNode
  where
    onOpenTag :: [Node] -> ByteString -> [Node]
    onOpenTag stack name = (Node name [] [] : stack)

    onAttr [] key val = error ("Attribute seen with no open tag: " <> show key <> "=" <> show val <> "")
    onAttr (node : stack) key val =
      node { attributes = (key, val) : node.attributes } : stack

    onCloseTag [] endTag = error ("End tag seen without opening tag: " <> show endTag)
    onCloseTag [node] endTag =
      -- No parent; presumably done (though if there's another tag after – e.g. an xml fragment – this
      -- node would be treated as the parent of the next one ... But we expect complete and valid xml)
      [node]
    onCloseTag (node : parent : stack) endTag =
      -- Pop this node off the stack, put it into the child-list of the parent
      parent { children = reverseChildren node : parent.children } : stack

    onEndOpenTag [] _             = []
    onEndOpenTag (node : stack) _ = (reverseAttributes node : stack)

    onText       stack _ = stack
    onCDATA      stack _ = stack

    reverseChildren node = node { children = reverse node.children }
    reverseAttributes node = node { children = reverse node.children }

[unhammer]

I think the crash happens because

xeno/src/Xeno/DOM.hs

Lines 166 to 182 in 5cb8d5a

	-- Growing a large vector is slow, so we need to do it less times.
	-- We can predict final array size after processing some part (i.e. 1/4) of input XML.
	--
	-- predictGrowSize _bsStart _bsLen _index vecLen = round $ fromIntegral vecLen * (1.25 :: Double)
	predictGrowSize bsStart bsLen index vecLen =
	let -- at least 1 so we don't divide by zero below and end up with
	-- a negative grow size if (bsStart + bsLen - offset0) == 0
	processedLen = max 1 (distance bsStart offset0 + bsLen)
	-- 1. Using integral operations, such as
	-- "predictedTotalSize = (index * S.length str) `div` processedLen"
	-- cause overflow, so we use float.
	-- 2. Slightly enlarge predicted size to compensite copy on vector grow
	-- if prediction is incorrect
	k = (1.25 :: Double) * fromIntegral (S.length str) / fromIntegral processedLen
	predictedTotalSize = round $ fromIntegral index * k
	growSize = predictedTotalSize - vecLen
	in growSize

gives 4947042293253 as predicted grow size.

With printf-debugging of some variables in that function:

("index",703353)
("bsStart",0x0000000000000000)
("offset0",0x0000004210d04020)
("bsLen",0)
("processedLen",1)
("S.length str",5626811)
("k",7033513.75)
("predictedTotalSize",4947042996604)
("vecLen",703351)
("growSize",4947042293253)

(The function predictGrowSize bsStart bsLen index vecLen gets called like predictGrowSize name_start name_len (index + 5) (UMV.length v).)

I don't feel confident in what this function is supposed to do, I think maybe @dmalkr or @adamse would know more. Is it meant to be saying that "our vector is now n elts big, we are 1/4th of the way through str, so we should grow to 3*n?" If so, I can imagine the prediction gets very wrong if this is called when we are 1/5626811th of the way through str :) Does it make sense to just change max 1 to max someHigherNumber in order to clamp early predictions? (That at least solves it for my file, but I don't know what's a good constant to pick here.) Or maybe there's a more principled way?