Performance idea: Partition before executing current uniform indentation search
还没有人认领这个 Issue。
评估
- 难度
- 5/5
- 预计耗时
- 一周以上
- 新手友好度
- 20/100
- Issue 类型
- 功能
- 描述清晰度
- 需要澄清
- 活跃度
- 停滞
- 技术栈
- ruby
- 领域
- performance, tooling
调研方向
从 schneems/partition 分支上失败的测试开始,跟踪当前搜索算法对 Ripper.parse 的调用。阅读缩进和 kw/end 对的处理方式,然后将分区或更大的扩展步骤与现有行为进行比较。完成标准是:九千行的案例能够避免 timeout,同时保持语法错误结果的质量。
由索引模型根据 Issue 内容生成。
描述
This is a failing test: https://github.com/zombocom/dead_end/tree/schneems/partition. The file is nine thousand lines and it takes a tad over 1 second to parse which means it hits the timeout.
We are already fairly well optimized for the current algorithm so to be able to handle arbitrarily large-sized files we will need a different strategy.
The current algorithm takes relatively small steps in the interest in producing a good end result. That takes a long time.
Here's my general idea: We can split up the file into multiple large chunks before running the current fine-grained algorithm. At a high level: split up the file into 2 parts and see which holds the syntax error. If we can isolate the problem to only half the file then we've dropped processing time in half (relatively). We can run this partition step a few times.
The catch is that some files (such as the one in the failing test cannot be split without introducing a syntax error (since it starts with a class declaration and ends with an end). To account for this we will need to split in a way that's lexically aware.
For example on that file, I think the algorithm would determine that it can't do much with indentation 0 so it would have to go to the next indentation, there it could see there are N chunks of kw/end pairs, it could divide into N/2 and see if one of those sections holds all of the syntax errors. We could perform this division several times to arrive at a subset of the larger problem, then run the original search array on it.
The challenge is, that we will essentially need to build an inverse of the existing algorithm. Instead of starting with a single line and expanding towards indentation zero, we'll start with all the lines and reduce towards indentation max.
The expensive part is checking code is valid via Ripper.parse, sub dividing large files into smaller files can help us isolate problems sections with fewer parse calls, but we've got to make sure the results are as good.
An alternative idea would be to use the existing search/expansion logic to perform more expansions until a set of N blocks are generated then check all of them at once. Then once the document problem is isolated, go back and re-parse only the N blocks with the existing. Algorithm. (Basically the same idea as partitioning, but we're working from the same direction as the current algorithm, just taking larger steps (which means fewer Ripper.parse) calls. However we would still need a way to sub-divide the blocks with this process in the terminal case that the syntax error is on indentation zero and the document is massive and all within one kw/end pair.
- 主要语言
- Ruby
- 星标
- 350
- 派生
- 17
- 平均合并
- 48 分钟
- 30 天内合并 PR
- 5
贡献指南
这个仓库没有索引到贡献指南
从这里开始
- 先读完整个 Issue,再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库,在一个分支上完成修改。
- 提交 Pull Request,并在描述里引用这个 Issue 编号。
ruby/syntax_suggest 的其他 Issue
-
难度 4/5 3-5 天 新手友好度 38/100
ruby/syntax_suggest#258 · 6 条评论 ·
-
难度 4/5 3-5 天 新手友好度 30/100
ruby/syntax_suggest#206 ·
-
难度 4/5 3-5 天 新手友好度 42/100
ruby/syntax_suggest#205 · 1 条评论 ·
-
难度 4/5 3-5 天 新手友好度 35/100
ruby/syntax_suggest#171 · 3 条评论 ·
-
难度 2/5 1-3 小时 新手友好度 45/100
ruby/syntax_suggest#109 · 1 条评论 ·
查看 ruby/syntax_suggest 的全部 Issue
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 75/100
simp/pupmod-simp-simp#395 ·
-
难度 2/5 1-3 小时 新手友好度 80/100
simp/pupmod-simp-rsyslog#219 ·
-
难度 1/5 1 小时以内 新手友好度 90/100
simp/pupmod-simp-pupmod#256 ·
-
难度 1/5 1 小时以内 新手友好度 90/100
simp/pupmod-simp-sudo#150 ·
-
难度 1/5 1 小时以内 新手友好度 90/100