Optimizing an Important Atom Primitive

294 点作者 mrbogle将近 10 年前

18 条评论

jerf将近 10 年前

You know, it's funny how it's 2015 and we're just dripping with raw power on our developer machines, yet, open a few hundred kilobytes of text and accidentally invoke a handful of O(n^2) algorithms and blammo, there goes all your power. Sobering.Edit: We need a type system which makes O(n^2) algorithms illegal. (Yes... I know what I just dialed up. You can't see it, but I'm giving a very big ol' evil grin.)

评论 #9729817 未加载

评论 #9728380 未加载

评论 #9727909 未加载

评论 #9727965 未加载

评论 #9728088 未加载

评论 #9728432 未加载

评论 #9730182 未加载

martanne将近 10 年前

A piece table[0] solves this rather elegantly. Since it is a persistent data structure, a mark can be represented as a pointer into an underlying buffer. If the corresponding text is deleted, marks are updated automatically, since the pointer is no longer reachable from the piece chain. Lookup is linear[1] (or logarithmic if you store pieces in a balanced search tree) in the number of pieces i.e. non-consecutive editing operations.[0] <a href="https://github.com/martanne/vis#text-management-using-a-piece-tablechain" rel="nofollow">https://github.com/martanne/vis#text-management-using-a-piec...</a>[1] <a href="https://github.com/martanne/vis/blob/master/text.c#L1152" rel="nofollow">https://github.com/martanne/vis/blob/master/text.c#L1152</a>

评论 #9729876 未加载

dunstad将近 10 年前

I tried out Atom a few weeks ago. I loved the UI! Absolutely fantastic, beautiful, nothing but praise there.But I had so many issues with stability, and really missed small but important features that were present in my other editors. I also found that most of the plugins worked either poorly or sporadically.In the end, I decided that it was not worth either using Atom or spending time contributing to it when I have some "pretty close" solutions today. Definitely looking forward to the 1.0 version though, and hats off to all those spending their time contributing to it. I'm sure it's going to become something great!

评论 #9727975 未加载

评论 #9730265 未加载

Veedrac将近 10 年前

I actually just retried Atom yesterday. Aside from the normal complaints (it's sloooww, undo doesn't affect markers or selections), one thing that struck me is that markers can't be zero-width. Well, they can but they won't show up. I'm wondering if this is related to the technique mentioned here - it's certainly been a pain to work around. Sublime Text even has multiple options for this (DRAW_EMPTY and DRAW_EMPTY_AS_OVERWRITE).That said, I'm loving the API design. Coming from Sublime Text, it's a massive upgrade. The ability to embed literally anything a web browser can render in a well-designed framework is mindblowing.

评论 #9728506 未加载

twic将近 10 年前

Didn't the Xanadu project solve this problem in 1972?<a href="https://en.wikipedia.org/wiki/Enfilade_%28Xanadu%29" rel="nofollow">https://en.wikipedia.org/wiki/Enfilade_%28Xanadu%29</a>Solve it, keep it secret, and then fail to properly write about it to this day.

评论 #9728400 未加载

drewm1980将近 10 年前

I really, really, don't get the whole "implement everything using web technologies" thing. As an outsider from that dev ecosystem it looks like the youtube videos you see of people implementing electronic circuits in Minecraft.

评论 #9730810 未加载

评论 #9730846 未加载

Erwin将近 10 年前

If you thought this was an interesting article, here 's the obligatory link to just about the only book on crafting a text editor, "Craft of Text Editing": <a href="http://www.finseth.com/craft/" rel="nofollow">http://www.finseth.com/craft/</a>

octref将近 10 年前

Recently I learned all contributors will receive a gift for Atom pre-1.0, and when I asked a Github stuff when will I receive the gift (I'm moving during this summer) he mentioned it would be sent out in early July. I guess we can expect a pre-1.0 before August.One of the main remaining functionality to be implemented is good support for large files. Looking at this issue [1], it seems Atom team is making some progress but there are still some problems to be tackled.In 0.208.0 (released 7 days ago) they mentioned in the changelog Atom now opens files larger than 2MB with syntax highlighting, soft wrap, and folds disabled. We'll work on raising the limits with these features enabled moving forward. Little bit disappointed at the progress as you could open large file with these features disabled long time ago through a package "view-tail-large-files".Just updated to 0.209.0 and using ember.js (1.9 MB) to test. Editing/scrolling has some delays but it's better than previous versions.Good luck Atom team![1]: <a href="https://github.com/atom/atom/issues/307#event-325455529" rel="nofollow">https://github.com/atom/atom/issues/307#event-325455529</a>

revelation将近 10 年前

Yet, the onKeyDown handler still takes 50ms. Are you kidding me? You can push a billion tris in that time.

评论 #9728098 未加载

ohitsdom将近 10 年前

Appreciate the candidness of the team writing about their naive approach. Definitely would have been a simpler fix to just search the currently visible text, but I'm glad they fixed the root issue to make markers more efficient for all.

alexchamberlain将近 10 年前

What is the data structure used for the text itself? A rope? The markers could be stored as offsets to the substrings themselves.

msoad将近 10 年前

This kind of knowledge and experience exists in Microsoft campus for years thanks to Visual Studio team. That's why Code is much more efficient. I only wish if it was open source so I could totally move away from Sublime Text.

评论 #9728725 未加载

romaniv将近 10 年前

This reminds me of how I re-implemented nested sets in relational databases as spans in a "coordinate" system.<pre><code> | Root | | Node | Node| | Node | Node | </code></pre> I stored only "X" and "Y" coordinates for every node, so you had to read "next" node in a row to get current node's "size".It was a bit more human-readable when looking at the data. More importantly, it reduced (on average) the number of nodes I needed to update on insert compared to nested set and gave an easy way of retrieving immediate children. But you still had to "move over" all the nodes "right" of the one you're inserting.The structure in the article looks eerily similar. I wonder whether it's somehow possible to apply GitHub's optimization to this "coordinate" based schema and make it relative without messing up the benefits of column indexing. Hm...

评论 #9728222 未加载

imslavko将近 10 年前

Vim also has a similar optimization: when a file changes, Vim only runs syntax highlighter on a visible part of the text + some buffer in both directions.

评论 #9728115 未加载

caiob将近 10 年前

Does it open files >2mb yet? My terminal vim does.

评论 #9728040 未加载

评论 #9728437 未加载

评论 #9729247 未加载

评论 #9728343 未加载

评论 #9728026 未加载

asQuirreL将近 10 年前

Hmmm... So the article seems to suggest that for every insertion of a character, a log time lookup is made. Is that really the case? If so, why is the leaf node that the cursor is in not saved? If you were to use a B+-tree implementation then you would already have access to neighbour pointers for rebalancing purposes, making the majority of incremental changes very cheap (constant time). This is just a thought, there may be good reasons why it's not possible.

baldfat将近 10 年前

Atom is still a hog on my main programing machine. It makes it unusable for me still.It is an OLD i3 Dell from 6 years ago desktop.

评论 #9727903 未加载

评论 #9728650 未加载

评论 #9727819 未加载

评论 #9727814 未加载

z3t4将近 10 年前

One thing I love about vanilla JS is that you can both set and get with the same property. I wonder if having both setters and getters is enforced by CoffeeScript or a design decision of the Atom team!?