Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incremental parser leaks space? #105

Open
ethercrow opened this issue Nov 19, 2012 · 69 comments

Comments

@ethercrow
Copy link
Member

commented Nov 19, 2012

Original author: reiner.p...@gmail.com (May 24, 2011 08:45:03)

What steps will reproduce the problem?
Use yi for a while, editing Haskell files with the Haskell mode (cleverMode). Over time, the memory consumption increases. I have found it quite typical for yi to consume around 300MB after I have used it for around 30mins.

Running 'reload' drops the memory use to much less -- often around 30MB.

The attached heap profile suggests that the incremental parser is mostly responsible.

Original issue: http://code.google.com/p/yi-editor/issues/detail?id=356

@ghost

This comment has been minimized.

Copy link

commented Apr 14, 2015

The issue seems to be that the incremental parser uses too much memory (confirmed in Haskell precise mode as well). The more the file gets traversed, the higher the memory consumption. The memory consumption does seem to stay constant once the entire file has been traversed, so the issue is just that the parser uses too much space. This is a big issue, since, the amount of space required to traverse the entire file is about 2GB for a Haskell file which is 50k sloc and 1MB in size.

@ghost

This comment has been minimized.

Copy link

commented Dec 12, 2016

Here's a heap profile using Haskell mode to show the space leak in the Incremental parser:

heap_profile

Syntax highlighting for Python does much better in this regard:

better_heap_profile

The operations I was performing was traversing the file with no changes to the file itself. Towards the end, you can see that the memory usage stays consistent since the entire file has been traversed.

I can verify that the parser runs in constant memory with the default mode (that is, no syntax highlighting). This is what the heap profile look like in this case:

heap_profile_default

So Haskell mode is forcing the Incremental parser to evaluate unnecessarily.

@ghost

This comment has been minimized.

Copy link

commented Dec 13, 2016

Profiling data seems to indicate that our culprit is getIndexedStream in

(\idx -> getIndexedStream Forward idx fb)
which is forcing the text. We would ideally like to be able to traverse the YiString somehow without keeping it in memory.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 20, 2016

From the comment it seems that @Fuuzetsu already suspected getIndexedStream would become a bottleneck.

-- | TODO: This guy is a pretty big bottleneck and only one function
-- uses it which in turn is only seldom used and most of the output is
-- thrown away anyway. We could probably get away with never
-- converting this to String here. The old implementation did so
-- because it worked over ByteString but we don't have to.

@ghost

This comment has been minimized.

Copy link

commented Dec 20, 2016

@noughtmare Yes. There was a discussion about this a long time ago on IRC. Should have had the discussion here instead. The issue is not specific to Haskell mode, rather, it's syntax highlighting in general.

I think getIndexedStream was suspected to be a CPU bottleneck. Here it's causing a space leak. Not exactly the same, but getting rid of it is beneficial regardless.

Modifying the syntax highlighter such that it doesn't need to use getIndexedStream would probably be the way to go:

, hlRun = updateCache

Or, at the very least, figure out why it's forcing the incremental parser.

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 21, 2016

Modifying the syntax highlighter such that it doesn't need to use getIndexedStream would probably be the way to go

Yes, the problem is that IIRC it's non-trivial which is why the function stuck around to begin with.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 21, 2016

Why is the getIndexedStream function bad, is it because it returns a list? Could we use one of the streaming libraries (like pipes or conduits) to circumvent this?

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 21, 2016

Everything is implemented in terms of YiString (which IIRC provided great speedup and much joy all around). It's implemented as a rope with chunks of Text. Here we call toString which unchunks the tree, unpacks concats the Text chunks, unpacks into String, potentially reverses the whole thing (yes, whole buffer), throws away some part of it and then returns the rest of the string chunked into 1 character each. As you can imagine, this isn't fast. Streaming libraries don't really help because implementation will have to be changed anyway.

I suppose the least painful improvement would be to write some functions in yi-rope which instead of doing all of the above provided the caller with some sort of an iterator that walks over the YiString directly. This could be better.

I have a bunch of time off work from tomorrow so maybe I could look into it if you can't/don't want to but I've been known to say that then disappear!

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 21, 2016

Would just using a foldl' be more memory efficient than the current situation?
We could then make a field of the Highlighter be a function like:

hlStep :: State a -> Text -> State a

Or do you mean that 'walking' the YiString from 'left' to 'right' is not the way to go?

@ghost

This comment has been minimized.

Copy link

commented Dec 21, 2016

@Fuuzetsu go for it. I'll try picking up in a few weeks if you do disappear.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 21, 2016

I could look into it if you can't/don't want to

I intend to look into this further (I think this issue might be related to the problems I'm facing with #946). But any help is very much appreciated!

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 22, 2016

I'm saying we can walk it but the way we're doing it right now is awful. It might have worked many years ago when the stream would have been produced lazily but in this case I believe we're going all out and then walking a forced stream. I think, I don't have data on hand.

Profile the function and see what it does.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 25, 2016

The fastMode for haskell seems to be the exact same as the clevermode but then without the Incremental Parser overhead.

fastMode:
yi

cleverMode:
yi

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 26, 2016

Ok, I think I found the problem. The Highlighter caches every step of the making of the abstract syntax tree All these states are being cached to speed up the generation of the AST when the buffer is edited (which naturally takes a lot of memory).

A solution to this would be to not cache any state at all, at the cost of more cpu time.

I think that we could also save a lot of memory by caching the state between a point and the previous point instead of caching all state up to a point for every point (this might not help because of laziness).

This is wrong :(.

PS: I don't think this bug is caused by the transition to the yi-rope type, because it was filed in 2011 (I believe yi-rope was made around 2014).

@ghost

This comment has been minimized.

Copy link

commented Dec 26, 2016

@noughtmare Can you verify that? I believe I tried turning caching off at some point, and didn't see a difference.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 27, 2016

I have some results:
The unfoldLexer function was to blame for the largest memory usage (in the fastMode for haskell). I just added a pair of seqs:

unfoldLexer :: ((state, input) -> Maybe (token, (state, input)))
            -> (state, input) -> [(state, token)]
unfoldLexer f b = fst b `seq` snd b `seq` case f b of
             Nothing -> []
             Just (t, b') -> (fst b, t) : unfoldLexer f b'

This removes part of the space leak.

Edit:
I guess just

unfoldLexer f b = fst b `seq` case f b of

is enough.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 27, 2016

Here are the graphs.

fastMode:
yi

cleverMode:
yi

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 27, 2016

What's your test.hs?

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 27, 2016

same as #105 (comment).
A 618 KB haskell file with just the Data.Data module (first thing I found) pasted into it many times.

@ghost

This comment has been minimized.

Copy link

commented Dec 27, 2016

@Fuuzetsu This pattern should work:

main :: IO ()
main = do
    putStrLn "Hèllo"
    putStrLn "Hèllo"
    putStrLn "Hèllo"
    putStrLn "Hèllo"
    putStrLn "Hèllo"
    putStrLn "Hèllo"
    putStrLn "Hèllo"
    putStrLn "Hèllo"

going on till infinity.... (95k lines in my case)

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 27, 2016

OK, I'm going to have some fun I think; do you have any more changes except the above strictness change?

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 27, 2016

No, that's it.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Dec 27, 2016

I get even better space usage when adding strictness in Yi.IncrementalParse.scanner.updateState0:

updateState0 curState toks@((st,tok):rest) = nextState `seq` ((st, curState), result) : updateState0 nextState rest

fastMode:
yi

cleverMode:
yi

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 27, 2016

Both the strictness annotations (use BangPatterns instead of seq) while potentially useful (in unfoldLexer the tuple constructor can be forced without bad effect at least I believe) miss the main issue. You should ask yourself "why am I seeing 200-300MB when I open the file"?

It can be quickly answered by looking into the incremental parsing paper (see README) then starting Yi on big file, editing first line then checking the heap. You'll find that memory usage does not go down when you compare this to going to the end of the file, back and editing the first line. Notably, we're not parsing incrementally currently. The whole point of the incremental parser is that we only parse up to the point we display on screen. If we change something then everything past the point of change to the point of current view should be parsed but nothing more. I recommend retainer profiling with -R20 if you want to see what needs fixing for yourself. I have found what I think is the main issue and checking potential fixes.

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 28, 2016

I suppose a picture speaks thousand words so

1482886543

This is loading nearly 1MB file with clever Haskell, down from 300-350MB to ~5MB: just opening file without moving anywhere. I still see some other problems though so not submitting anything yet.

There is of course a lot of value of looking for improving worst case (i.e. what you're seeing above) so I encourage you to pursue it but just be aware of what you're measuring.

EDIT: For reference, here is the real problem we're looking to fix:

1482887113

The above is from going to the end of the file (so as expected we parse everything and have huge spike) but then we return to beginning and type some stuff in: the memory stays way too high even after the parse should have been discarded (AFAICT).

@ghost

This comment has been minimized.

Copy link

commented Dec 28, 2016

Interesting. Wasn't aware of retainer profiling. Makes it so much easier.

Fixing the memory issue in Vty refresh function (Vty.hs#L212) with that becomes fairly trivial:

        (miniImages, bigImages) = let f = fmap (picture . snd) in bimap f f
                                $ partition (isMini . fst) (toList windowsAndImages)

EDIT: nevermind, the size of the list is too small to matter.

@Fuuzetsu are you considering Pango as well?

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Dec 28, 2016

@siddhanathan There is a much worse problem than lack of sharing there. The sizes used for rendering text and obtaining strokes is completely wrong: it's using Rect size which is a pixel size to specify number of characters; so on 1080p screen, we're saying "render next 2million characters". This was responsible for whole file being parsed as soon as you opened. The fix there is simple (and can be improved) and gets rid of indexed stream usage. I inline some of it here though I'll likely send a PR some time.

@@ -66,6 +66,7 @@ import           Yi.Config
 import           Yi.Debug                       (logError, logPutStrLn)
 import           Yi.Editor
 import           Yi.Event                       (Event)
+import qualified Yi.Rope as R
 import           Yi.Style
 import           Yi.Types                       (YiConfigVariable)
 import qualified Yi.UI.Common                   as Common
@@ -74,7 +75,7 @@ import           Yi.Layout                      (HasNeighborWest)
 import           Yi.UI.TabBar                   (TabDescr (TabDescr), tabBarDescr)
 import           Yi.UI.Utils                    (arrangeItems, attributesPictureAndSelB)
 import           Yi.Frontend.Vty.Conversions          (colorToAttr, fromVtyEvent)
-import           Yi.Window                      (Window (bufkey, isMini, wkey))
+import           Yi.Window                      (Window (bufkey, isMini, wkey, width, height))
 
 
 data Rendered = Rendered
@@ -240,10 +241,12 @@ refresh fs e = do
         { Vty.picCursor = cursorPos }
 
 renderWindow :: UIConfig -> Editor -> SL.Rect -> HasNeighborWest -> (Window, Bool) -> Rendered
-renderWindow cfg e (SL.Rect x y w h) nb (win, focused) =
+renderWindow cfg e (SL.Rect x y _ _) nb (win, focused) =
     Rendered (Vty.translate x y $ if nb then vertSep Vty.<|> pict else pict)
              (fmap (\(i, j) -> (i + y, j + x')) cur)
     where
+        w = Yi.Window.width win
+        h = Yi.Window.height win
         x' = x + if nb then 1 else 0
         w' = w - if nb then 1 else 0
         b = findBufferWith (bufkey win) e
@@ -257,21 +260,25 @@ renderWindow cfg e (SL.Rect x y w h) nb (win, focused) =
         wsty = attributesToAttr ground Vty.defAttr
         eofsty = appEndo (eofStyle sty) ground
         (point, _) = runBuffer win b pointB
-        region = mkSizeRegion fromMarkPoint $ Size (w' * h')
+        (text, _) = runBuffer win b $
+          -- Take the window worth of lines; we now know exactly how
+          -- much text to render, parse and stroke.
+          fst . R.splitAtLine h' <$> streamB Forward fromMarkPoint
+
+        region = mkSizeRegion fromMarkPoint . Size $! R.length text
         -- Work around a problem with the mini window never displaying it's contents due to a
         -- fromMark that is always equal to the end of the buffer contents.
         (Just (MarkSet fromM _ _), _) = runBuffer win b (getMarks win)
         fromMarkPoint = if notMini
                         then fst $ runBuffer win b $ use $ markPointA fromM
                         else Point 0
-        (text, _) = runBuffer win b (indexedStreamB Forward fromMarkPoint)
 
         (attributes, _) = runBuffer win b $ attributesPictureAndSelB sty (currentRegex e) region
         -- TODO: I suspect that this costs quite a lot of CPU in the "dry run" which determines the window size;
         -- In that case, since attributes are also useless there, it might help to replace the call by a dummy value.
         -- This is also approximately valid of the call to "indexedAnnotatedStreamB".
         colors = map (fmap (($ Vty.defAttr) . attributesToAttr)) attributes
-        bufData =  paintChars Vty.defAttr colors text
+        bufData =  paintChars Vty.defAttr colors $! zip [fromMarkPoint..] (R.toString text)

However it doesn't fix the problem fully: if we go back to the start of file and change it, the memory does not go back to what it was when we initially opened the file. Something is holding onto parser state and that's what I'm trying to find now.

Lastly, no, I'm not looking at Pango right this second; I want to finally remove all the gtk2 code and migrate it to gtk3 before doing anything else there. It also obfuscates profiling information because it's much more resource intensive than Vty so I'm working with that right now.

Edit: having said that, it is nearly 5am here so feel free to go at it…

@ghost

This comment has been minimized.

Copy link

commented Dec 28, 2016

The profiler seems to be pointing towards updateCache in the highlighter:

updateCache newFileScan dirtyOffset (Cache path cachedStates oldResult _) = Cache path newCachedStates newResult M.empty

Becomes clear when we add -L100 to the RTS options.

@ghost

This comment has been minimized.

Copy link

commented Dec 29, 2016

Reached the same conclusion @Fuuzetsu reached a while ago. Something is holding on to the Parser state, but not using it.

bio

retainers

@ghost

This comment has been minimized.

Copy link

commented Dec 31, 2016

@noughtmare Instead of forcing values in unfoldLexer, we could make them lazier.

diff --git a/yi-language/src/Yi/Lexer/Alex.hs b/yi-language/src/Yi/Lexer/Alex.hs
index ccd15471..f1ba7be6 100644
--- a/yi-language/src/Yi/Lexer/Alex.hs
+++ b/yi-language/src/Yi/Lexer/Alex.hs
@@ -212,9 +212,9 @@ lexScanner Lexer {..} src = Scanner
 -- | unfold lexer into a function that returns a stream of (state, token)
 unfoldLexer :: ((state, input) -> Maybe (token, (state, input)))
             -> (state, input) -> [(state, token)]
-unfoldLexer f b = case f b of
+unfoldLexer f ~(s, i) = case f (s, i) of
              Nothing -> []
-             Just (t, b') -> (fst b, t) : unfoldLexer f b'
+             Just ~(t, ~b') -> (s, t) : unfoldLexer f b'
 
 -- * Lenses
 makeLensesWithSuffix "A" ''Posn

This has the same effect, and reduces memory consumption in fastmode by over 50% in my tests. Using strictness annotations here would unnecessarily force the incremental parser.

@ghost

This comment has been minimized.

Copy link

commented Jan 6, 2017

I'm curious about the performance impact of the patch I posted above. And maybe evaluating other ways of having a cache that doesn't keep the incremental parser state around unnecessarily. That patch simply makes syntax highlighting non-incremental, which might not be what we want.

Making apply strict

Experimenting is fine. But there's a very good reason that application is lazy. Rather than blaming the incremental parser, try blaming the entity using the incremental parser incorrectly. In this case, what is doing the call to apply, and is that call retaining memory unnecessarily (checked via a biography profile).

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 6, 2017

yi: internal error: Invalid object in processHeapClosureForDead(): 131184
    (GHC version 8.0.1 for x86_64_unknown_linux)
    Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug
[1]    11407 abort (core dumped)  yi -fvty -kvim test.hs +RTS -hbdrag,void -hc

😞

@ghost

This comment has been minimized.

Copy link

commented Jan 6, 2017

@noughtmare Leave a comment here https://ghc.haskell.org/trac/ghc/ticket/7836 . If you have reproducible steps, then mention them in the bug.

@ghost

This comment has been minimized.

Copy link

commented Jan 7, 2017

I'm guessing some part of syntax highlighting is holding on to the lexer state.

EDIT: Nevermind. That memory is actually used.

Clever mode:

alex

Fast mode:

fastmode

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2017

More results!

diff --git a/yi-keymap-vim/src/Yi/Keymap/Vim/StateUtils.hs b/yi-keymap-vim/src/Yi/Keymap/Vim/StateUtils.hs
index a694c1f6..b288e2c1 100644
--- a/yi-keymap-vim/src/Yi/Keymap/Vim/StateUtils.hs
+++ b/yi-keymap-vim/src/Yi/Keymap/Vim/StateUtils.hs
@@ -91,7 +91,7 @@ flushAccumulatorE :: EditorM ()
 flushAccumulatorE = do
     accum <- vsAccumulator <$> getEditorDyn
     let repeatableAction = stringToRepeatableAction accum
-    modifyStateE $ \s ->
+    accum `seq` modifyStateE $ \s ->
         s { vsRepeatableAction = Just repeatableAction
           , vsAccumulator = mempty
           , vsCurrentMacroRecording = fmap (fmap (<> accum))
diff --git a/yi-language/src/Yi/Lexer/Alex.hs b/yi-language/src/Yi/Lexer/Alex.hs
index ccd15471..a9a273e7 100644
--- a/yi-language/src/Yi/Lexer/Alex.hs
+++ b/yi-language/src/Yi/Lexer/Alex.hs
@@ -212,7 +212,7 @@ lexScanner Lexer {..} src = Scanner
 -- | unfold lexer into a function that returns a stream of (state, token)
 unfoldLexer :: ((state, input) -> Maybe (token, (state, input)))
             -> (state, input) -> [(state, token)]
-unfoldLexer f b = case f b of
+unfoldLexer f b = fst b `seq` case f b of
              Nothing -> []
              Just (t, b') -> (fst b, t) : unfoldLexer f b'

before:
yi-before

after:
yi-after

I've gotten rid of the memory leak 😃!

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2017

One more thing.
My routine for this test was first open a big file (same as above), then press 'G' (to force the highlighter) then 'vggd' (delete the entire file) then 'i' and entering some random text, then 'upG' (undoing, pasting in the original file and scrolling down) and then some cursor movement and finally ':q!' (to quit).

As you can see in the after picture there is a moment (around the 2 sec mark) where the memory is constant. I think this is the time when I entered the random text. It should be possible to already release the memory there, but I don't know how.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2017

I forgot to add results for other modes.

Precise mode
Before
yi-before-precise

After
yi-after-precise

Clever mode:
Before
yi-before-clever

After
yi-after-clever

@ghost

This comment has been minimized.

Copy link

commented Jan 18, 2017

So if I understand correctly, it makes things worse in precise mode. As Fuuzetsu mentioned, a bang pattern on b does the job perfectly fine, and should give similar results in both modes.

What is actually happening is quite simple. The syntax driver holds on to the list of parser states in its cache. This is okay, because it's not using those parser states before the user starts editing the text. To verify that, ensure that updateCache is called only once when casually scrolling. The space complexity of this is O(n) as proposed by Jean-Philippe Bernardy, where n is the cursor position where the edit occurs. When no edits occur, this should use negligible space. On the contrary, what we're seeing is that scrolling the window pane forces this list. My guess would be that some part of the program related to focusing is evaluating the parser state independently and throwing it away. Even though that seems harmless, because of sharing and memoization, it has the side effect of forcing the list of parser states held in the syntax driver.

The other issue that I had since the very beginning is, even if we do manage O(n) space complexity, the actual space being used is a lot. The way incremental parsing is done right now essentially rules out the possibility of using Yi with big data files. It is a tradeoff between space/time, and that's understandable, but it's a tradeoff we need to be aware about (gigabytes of memory for a megabyte text file is a lot!). One way to reduce the space usage further is to parse chunks at a time (and this might fit nicely with the rope structure we are using), and store the state of parsing chunks. This way, we don't store the intermediate parse state after parsing every character. The results would be less online-ish, but at least use significantly less space.

@ethercrow @Fuuzetsu any thoughts on replacing the character scanners with chunk scanners?

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2017

The performance has not degraded, I will post the befores.

Edit: I've added them to my previous post.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2017

This is strange, I just press 'G' in the file and then when it is done ':q!' (precise mode):
yi-strange

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 19, 2017

I just noticed that the precise parser is (even without the strictness changes) not usable. I opened yi-core/src/Parser/Incremental.hs and pressed x somewhere in the middle of the file and Yi just froze and started consuming all my memory. I had to kill it forcefully.

Heap profile:
yi

@noughtmare noughtmare added this to the 0.14 milestone Jan 26, 2017

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 26, 2017

I dicovered something else. The large spikes in the precise mode are due to a bug in the parser (might be related to #141), here's a heap of a different file with ~20K lines (657KB):

yi-withoutbug

400 MB is a lot better than 1GB.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 26, 2017

The new picture of the scroll down -> delete entire buffer -> waste some time -> paste -> scroll down again, looks very much like the clevermode one:

yi-without

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 26, 2017

The strange thing about the incrementalparse parsers is that the toP and iBest data persists even when the entire buffer is deleted and it doesn't generate a new data when pasting it back in, which makes me believe the memory usage is unnecessary.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 27, 2017

The nocache syntax driver proposed by @siddhanathan makes the preciseMode use only 25MB! This gives me even more confidence in the fact that the 300MB memory usage is unnecessary!

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 27, 2017

I think I fixed it:

diff --git a/yi-core/src/Yi/Syntax/Driver.hs b/yi-core/src/Yi/Syntax/Driver.hs
index f62a4b7e..ca0e5ca1 100644
--- a/yi-core/src/Yi/Syntax/Driver.hs
+++ b/yi-core/src/Yi/Syntax/Driver.hs
@@ -45,7 +45,7 @@ mkHighlighter scanner =
                   newCachedStates = reused ++ fmap fst recomputed
                   recomputed = scanRun newScan resumeState
                   newResult :: tree (Tok tt)
-                  newResult = if null recomputed then oldResult else snd $ head recomputed
+                  newResult = if null recomputed then oldResult else snd $ head $ scanRun newScan $ if null reused then scanInit (scanner newFileScan) else last reused
           focus r (Cache path states root _focused) =
               Cache path' states root focused
               where (path', focused) = unzipFM $ zipWithFM (\newpath oldpath -> fromNodeToFinal newpath (oldpath,root)) [] r path

Precise mode before:

yi-without

after:

yi-fixed

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 27, 2017

Unfortunantly, inserting text at the end of the file still causes 300MB to be used.

@ghost

This comment has been minimized.

Copy link

commented Jan 28, 2017

Unfortunantly, inserting text at the end of the file still causes 300MB to be used.

Wait, that is the behavior we want. Scrolling through the file shouldn't cause any memory consumption.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 28, 2017

@siddhanathan Shouldn't we want to cache intermediate states while parsing and parse while scrolling (and therefore consume memory while scrolling)?

I think that the reason for the high memory usage is that we're reparsing the file for every intermediate state that we cache.

The fact that it is possible to scroll the file without causing all the memory to be consumed means that it at least parses the file twice, once to get the final result and another time to find the intermediate state (which defeats the purpose of caching the states).

The mkHighlighter function only uses the head of the recomputed list of states, which is essential for the lazy parsing, but it also means that its not caching the intermediate states while parsing (because it will only cache the intermediate states when it uses the later elements of the scanner).

@ghost

This comment has been minimized.

Copy link

commented Jan 29, 2017

Shouldn't we want to cache intermediate states while parsing and parse while scrolling (and therefore consume memory while scrolling)?

Parsing is an expensive operation. So no. It would cause scrolling to be slow.

it at least parses the file twice, once to get the final result and another time to find the intermediate state (which defeats the purpose of caching the states).

using different representations, so this should hopefully be okay.

I think that the reason for the high memory usage is that we're reparsing the file for every intermediate state that we cache.

Maybe. I'm not sure. I can verify that your patch does improve memory usage.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 29, 2017

Ah, I meant that we're parsing while scrolling down for the first time. Subsequent scrolling won't cause any additional memory usage.

@ghost

This comment has been minimized.

Copy link

commented Jan 29, 2017

Ah, I meant that we're parsing while scrolling down for the first time

Yes. That bothers me though. I don't think that should happen. My guess is, something somewhere is innocently using the parser without requiring too much memory - without realizing that it is forcing the parse state which results in higher memory usage for the syntax driver. Which is also why identifying the problem is difficult, it's not the function with the highest memory usage which is the root cause here.

Now we do need high memory usage when editing the file, but that is proportional to the position of the edit, so if the user edits the file at the beginning, I would hope the memory usage would not be very high. Lowering this memory consumption would be a separate issue, because that could compromise performance.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 29, 2017

I think it was designed to lazily parse the file so that it can display the file immediately on opening (even for very very very big files).

from yi-editor.github.io:

Hughes and Swierstra have shown how online parsers can be constructed. An online parser takes advantage of lazy evaluation: the input is analyzed only as far as needed to produce the part of the result that is forced.

Effectively, this solves part of the incremental parsing problem: since the user can see only one page of text at a time, the editor will only force so much of the result tree, and only the corresponding part of the input will be analyzed, making the parser response time independent of the length of the input.

@noughtmare

This comment has been minimized.

Copy link
Contributor

commented Jan 29, 2017

using different representations, so this should hopefully be okay.

It should work, but only after the first change. The first change causes the intermediate state(s) to be calculated, the parser can only use the saved state on subsequent changes.

Oh, I realize now that it used to calculate the intermediate states on the first parse, before the change I suggested two days ago. So without that change it works correctly (I mean it works as intended).

@Fuuzetsu

This comment has been minimized.

Copy link
Member

commented Jan 30, 2017

Yes. That bothers me though. I don't think that should happen.

It should and it's by design: how else are we going to display syntax highlighting to the user if we don't parse until the point user is viewing?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.