{"action":"created","issue":{"url":"https://api.github.com/repos/greghendershott/markdown/issues/43","labels_url":"https://api.github.com/repos/greghendershott/markdown/issues/43/labels{/name}","comments_url":"https://api.github.com/repos/greghendershott/markdown/issues/43/comments","events_url":"https://api.github.com/repos/greghendershott/markdown/issues/43/events","html_url":"https://github.com/greghendershott/markdown/issues/43","id":37519444,"number":43,"title":"performance experiments","user":{"login":"stchang","id":28650,"avatar_url":"https://avatars.githubusercontent.com/u/28650?v=3","gravatar_id":"","url":"https://api.github.com/users/stchang","html_url":"https://github.com/stchang","followers_url":"https://api.github.com/users/stchang/followers","following_url":"https://api.github.com/users/stchang/following{/other_user}","gists_url":"https://api.github.com/users/stchang/gists{/gist_id}","starred_url":"https://api.github.com/users/stchang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stchang/subscriptions","organizations_url":"https://api.github.com/users/stchang/orgs","repos_url":"https://api.github.com/users/stchang/repos","events_url":"https://api.github.com/users/stchang/events{/privacy}","received_events_url":"https://api.github.com/users/stchang/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2014-07-09T23:37:44Z","updated_at":"2015-06-10T21:29:41Z","closed_at":null,"body":"I've been trying to improve the performance of the markdown parser through `parsack` improvements but haven't had much luck so far. I think it's just the bracketed-style of the grammar leads to too much backtracking, which my parser doesn't handle well.\r\n\r\nThat did give me an idea to profile some examples (ie your tests) to see if I could improve the ordering on any of the `<or>` options, to cut down on the backtracking.\r\n\r\nFor example the following changes produces a decent speedup of `perf-test.rkt`:\r\n\r\n1. Flip the choices in `$normal-char`.\r\n2. Remove the singleton `<or>` in `source-url`.\r\n3. In `$inline`, drop `$smart-punctuation` down to above `$code`.\r\n4. In `$inline`, drop the `4+ ...` down to above `$footnote-ref`.\r\n\r\nObvious caveats:\r\n1. I don't know how representative `perf-tests.rkt` is.\r\n2. I know sometimes the order of the `<or>` choices matters, when the choices are not disjoint, so I don't know if I've actually messed something up. But all the tests do pass.\r\n3. I do occasionally get a perf warning from `random-test.rkt`. I guess this is unsurprising since `random-test` emphasizes special chars?\r\n\r\nSome numbers:\r\n\r\nBefore: non-strict: `3200`, strict: `3340`\r\nAfter: non-strict: `2598`, strict: `2547`\r\n\r\nHave you played around with the `<or>` ordering any?"},"comment":{"url":"https://api.github.com/repos/greghendershott/markdown/issues/comments/110920635","html_url":"https://github.com/greghendershott/markdown/issues/43#issuecomment-110920635","issue_url":"https://api.github.com/repos/greghendershott/markdown/issues/43","id":110920635,"user":{"login":"jbclements","id":226617,"avatar_url":"https://avatars.githubusercontent.com/u/226617?v=3","gravatar_id":"","url":"https://api.github.com/users/jbclements","html_url":"https://github.com/jbclements","followers_url":"https://api.github.com/users/jbclements/followers","following_url":"https://api.github.com/users/jbclements/following{/other_user}","gists_url":"https://api.github.com/users/jbclements/gists{/gist_id}","starred_url":"https://api.github.com/users/jbclements/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jbclements/subscriptions","organizations_url":"https://api.github.com/users/jbclements/orgs","repos_url":"https://api.github.com/users/jbclements/repos","events_url":"https://api.github.com/users/jbclements/events{/privacy}","received_events_url":"https://api.github.com/users/jbclements/received_events","type":"User","site_admin":false},"created_at":"2015-06-10T21:29:41Z","updated_at":"2015-06-10T21:29:41Z","body":"I ran into some severe issues using markdown on files containing lists. Specifically, I have a file with a list of length 1600, and... it takes a long, long time to process. I decided to run some experiments, using this file\r\n\r\n```racket\r\n#lang racket\r\n\r\n(require markdown/parse)\r\n\r\n(define markdown-header\r\n  #<<|\r\n# My beautiful Markdown File\r\n\r\nI have some things to say. Here they are:\r\n\r\n|\r\n  )\r\n\r\n(define (random-list-entry)\r\n  (define r (random-string))\r\n  (~a \"- [\"r\"](http://example.com/\"r\")\\n\"))\r\n\r\n(define (random-string)\r\n  (apply\r\n   string-append\r\n   (for/list ([i 5])\r\n     (bytes->string/utf-8 (bytes (+ (bytes-ref #\"a\" 0) (random 26)))))))\r\n\r\n(define (run-trial size)\r\n  (define f (make-temporary-file))\r\n  \r\n  (call-with-output-file f\r\n    (lambda (port)\r\n      (display markdown-header port)\r\n      (for ([i size])\r\n        (display (random-list-entry) port)))\r\n    #:exists 'truncate)\r\n  \r\n  (parse-markdown f))\r\n\r\n(for/list ([size (in-range 0 5000 500)])\r\n  (define-values (_1 cpu-msec _2 _3) (time-apply run-trial (list size)))\r\n  (printf \"(~a ~a)\\n\" size cpu-msec))\r\n```\r\n\r\nThen, I ran it for sizes from 0 up to 4500 in increments of 500, and plotted them. Here's my data:\r\n\r\n```racket\r\n#lang racket\r\n\r\n(require plot)\r\n\r\n\r\n(define data2\r\n  '((0 8)\r\n    (500 928)\r\n    (1000 3375)\r\n    (1500 6623)\r\n    (2000 11084)\r\n    (2500 17008)\r\n    (3000 24204)\r\n    (3500 33739)\r\n    (4000 43472)\r\n    (4500 56053)))\r\n\r\n(plot (list (lines data2)\r\n            (function (lambda (x)\r\n                        (* 0.0027 (* x x))))))\r\n```\r\n\r\n... and here's the result (the 0.0027 is just me trying to fit a curve):\r\n\r\n![screen shot 2015-06-10 at 2 27 16 pm](https://cloud.githubusercontent.com/assets/226617/8094568/d79ce524-0f7c-11e5-8275-011785dff9cc.png)\r\n\r\nBasically, it's n^2. \r\n\r\nI'm assuming that this is backtracking, probably on the \"is the list over yet\" rule.\r\n\r\nIs there any obvious way to restructure the parsing rules to speed this up? I would think this would be a standard problem for combinator-based parsers."}}