{"action":"created","issue":{"url":"https://api.github.com/repos/xtermjs/xterm.js/issues/791","repository_url":"https://api.github.com/repos/xtermjs/xterm.js","labels_url":"https://api.github.com/repos/xtermjs/xterm.js/issues/791/labels{/name}","comments_url":"https://api.github.com/repos/xtermjs/xterm.js/issues/791/comments","events_url":"https://api.github.com/repos/xtermjs/xterm.js/issues/791/events","html_url":"https://github.com/xtermjs/xterm.js/issues/791","id":242564306,"node_id":"MDU6SXNzdWUyNDI1NjQzMDY=","number":791,"title":"Buffer performance improvements","user":{"login":"Tyriar","id":2193314,"node_id":"MDQ6VXNlcjIxOTMzMTQ=","avatar_url":"https://avatars0.githubusercontent.com/u/2193314?v=4","gravatar_id":"","url":"https://api.github.com/users/Tyriar","html_url":"https://github.com/Tyriar","followers_url":"https://api.github.com/users/Tyriar/followers","following_url":"https://api.github.com/users/Tyriar/following{/other_user}","gists_url":"https://api.github.com/users/Tyriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Tyriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Tyriar/subscriptions","organizations_url":"https://api.github.com/users/Tyriar/orgs","repos_url":"https://api.github.com/users/Tyriar/repos","events_url":"https://api.github.com/users/Tyriar/events{/privacy}","received_events_url":"https://api.github.com/users/Tyriar/received_events","type":"User","site_admin":false},"labels":[{"id":323589242,"node_id":"MDU6TGFiZWwzMjM1ODkyNDI=","url":"https://api.github.com/repos/xtermjs/xterm.js/labels/type/proposal","name":"type/proposal","color":"fbca04","default":false}],"state":"open","locked":false,"assignee":{"login":"Tyriar","id":2193314,"node_id":"MDQ6VXNlcjIxOTMzMTQ=","avatar_url":"https://avatars0.githubusercontent.com/u/2193314?v=4","gravatar_id":"","url":"https://api.github.com/users/Tyriar","html_url":"https://github.com/Tyriar","followers_url":"https://api.github.com/users/Tyriar/followers","following_url":"https://api.github.com/users/Tyriar/following{/other_user}","gists_url":"https://api.github.com/users/Tyriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Tyriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Tyriar/subscriptions","organizations_url":"https://api.github.com/users/Tyriar/orgs","repos_url":"https://api.github.com/users/Tyriar/repos","events_url":"https://api.github.com/users/Tyriar/events{/privacy}","received_events_url":"https://api.github.com/users/Tyriar/received_events","type":"User","site_admin":false},"assignees":[{"login":"Tyriar","id":2193314,"node_id":"MDQ6VXNlcjIxOTMzMTQ=","avatar_url":"https://avatars0.githubusercontent.com/u/2193314?v=4","gravatar_id":"","url":"https://api.github.com/users/Tyriar","html_url":"https://github.com/Tyriar","followers_url":"https://api.github.com/users/Tyriar/followers","following_url":"https://api.github.com/users/Tyriar/following{/other_user}","gists_url":"https://api.github.com/users/Tyriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Tyriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Tyriar/subscriptions","organizations_url":"https://api.github.com/users/Tyriar/orgs","repos_url":"https://api.github.com/users/Tyriar/repos","events_url":"https://api.github.com/users/Tyriar/events{/privacy}","received_events_url":"https://api.github.com/users/Tyriar/received_events","type":"User","site_admin":false}],"milestone":null,"comments":44,"created_at":"2017-07-13T01:58:43Z","updated_at":"2018-07-24T16:36:53Z","closed_at":null,"author_association":"MEMBER","body":"## Problem\r\n\r\n**Memory**\r\n\r\nRight now our buffer is taking up too much memory, particularly for an application that launches multiple terminals with large scrollbacks set. For example, the demo using a 160x24 terminal with 5000 scrollback filled takes around 34mb memory (see https://github.com/Microsoft/vscode/issues/29840#issuecomment-314539964), remember that's just a single terminal and 1080p monitors would likely use wider terminals. Also, in order to support truecolor (https://github.com/sourcelair/xterm.js/issues/484), each character will need to store 2 additional `number` types which will almost double the current memory consumption of the buffer.\r\n\r\n**Slow fetching of a row's text**\r\n\r\nThere is the other problem of needing to fetch the actual text of a line swiftly. The reason this is slow is due to the way that the data is laid out; a line contains an array of characters, each having a single character string. So we will construct the string and then it will be up for garbage collection immediately afterwards. Previously we didn't need to do this at all because the text is pulled from the line buffer (in order) and rendered to the DOM. However, this is becoming an increasingly useful thing to do though as we improve xterm.js further, features like the selection and links both pull this data. Again using the 160x24/5000 scrollback example, it takes 30-60ms to copy the entire buffer on a Mid-2014 Macbook Pro.\r\n\r\n**Supporting the future**\r\n\r\nAnother potential problem in the future is when we look at introducing some view model which may need to duplicate some or all of the data in the buffer, this sort of thing will be needed to implement reflow (https://github.com/sourcelair/xterm.js/issues/622) properly (https://github.com/sourcelair/xterm.js/pull/644#issuecomment-298058556) and *maybe* also needed to properly support screen readers (https://github.com/sourcelair/xterm.js/issues/731). It would certainly be good to have some wiggle room when it comes to memory.\r\n\r\nThis discussion started in https://github.com/sourcelair/xterm.js/issues/484, this goes into more detail and proposes some additional solution.\r\n\r\nI'm leaning towards solution 3 and moving towards solution 5 if there is time and it shows a marked improvement. Would love any feedback! /cc @jerch, @mofux, @rauchg, @parisk \r\n\r\n## 1. Simple solution\r\n\r\nThis is basically what we're doing now, just with truecolor fg and bg added.\r\n\r\n```ts\r\n// [0]: charIndex\r\n// [1]: width\r\n// [2]: attributes\r\n// [3]: truecolor bg\r\n// [4]: truecolor fg\r\ntype CharData = [string, number, number, number, number];\r\n\r\ntype LineData = CharData[];\r\n```\r\n\r\n**Pros**\r\n\r\n- Very simple\r\n\r\n**Cons**\r\n\r\n- Too much memory consumed, would nearly double our current memory usage which is already too high.\r\n\r\n## 2. Pull text out of CharData\r\n\r\nThis would store the string against the line rather than the line, this would probably see very large gains in selection and linkifying and would be more useful as time goes on having quick access to a line's entire string.\r\n\r\n```ts\r\ninterface ILineData {\r\n  // This would provide fast access to the entire line which is becoming more\r\n  // and more important as time goes on (selection and links need to construct\r\n  // this currently). This would need to reconstruct text whenever charData\r\n  // changes though. We cannot lazily evaluate text due to the chars not being\r\n  // stored in CharData\r\n  text: string;\r\n  charData: CharData[];\r\n}\r\n\r\n// [0]: charIndex\r\n// [1]: attributes\r\n// [2]: truecolor bg\r\n// [3]: truecolor fg\r\ntype CharData = Int32Array;\r\n```\r\n\r\n**Pros**\r\n\r\n- No need to reconstruct the line whenever we need it.\r\n- Lower memory than today due to the use of an `Int32Array`\r\n\r\n**Cons**\r\n\r\n- Slow to update individual characters, the entire string would need to be regenerated for single character changes.\r\n\r\n## 3. Store attributes in ranges\r\n\r\nPulling the attributes out and associating them with a range. Since there can never be overlapping attributes, this can be laid out sequentially.\r\n\r\n```ts\r\ntype LineData = CharData[]\r\n\r\n// [0]: The character\r\n// [1]: The width\r\ntype CharData = [string, number];\r\n\r\nclass CharAttributes {\r\n  public readonly _start: [number, number];\r\n  public readonly _end: [number, number];\r\n  private _data: Int32Array;\r\n\r\n  // Getters pull data from _data (woo encapsulation!)\r\n  public get flags(): number;\r\n  public get truecolorBg(): number;\r\n  public get truecolorFg(): number;\r\n}\r\n\r\nclass Buffer extends CircularList<LineData> {\r\n  // Sorted list since items are almost always pushed to end\r\n  private _attributes: CharAttributes[];\r\n\r\n  public getAttributesForRows(start: number, end: number): CharAttributes[] {\r\n    // Binary search _attributes and return all visible CharAttributes to be\r\n    // applied by the renderer\r\n  }\r\n}\r\n```\r\n\r\n**Pros**\r\n\r\n- Lower memory than today even though we're also storing truecolor data\r\n- Can optimize application of attributes, rather than checking every single character's attribute and diffing it to the one before\r\n- Encapsulates the complexity of storing the data inside an array (`.flags` instead of `[0]`)\r\n\r\n**Cons**\r\n\r\n- Changing attributes of a range of characters inside another range is more complex\r\n\r\n## 4. Put attributes in a cache\r\n\r\nThe idea here is to leverage the fact that there generally aren't that many styles in any one terminal session, so we should not create as few as necessary and reuse them.\r\n\r\n```ts\r\n// [0]: charIndex\r\n// [1]: width\r\ntype CharData = [string, number, CharAttributes];\r\n\r\ntype LineData = CharData[];\r\n\r\nclass CharAttributes {\r\n  private _data: Int32Array;\r\n\r\n  // Getters pull data from _data (woo encapsulation!)\r\n  public get flags(): number;\r\n  public get truecolorBg(): number;\r\n  public get truecolorFg(): number;\r\n}\r\n\r\ninterface ICharAttributeCache {\r\n  // Never construct duplicate CharAttributes, figuring how the best way to\r\n  // access both in the best and worst case is the tricky part here\r\n  getAttributes(flags: number, fg: number, bg: number): CharAttributes;\r\n}\r\n```\r\n\r\n**Pros**\r\n\r\n- Similar memory usage to today even though we're also storing truecolor data\r\n- Encapsulates the complexity of storing the data inside an array (`.flags` instead of `[0]`)\r\n\r\n**Cons**\r\n\r\n- Less memory savings than the ranges approach\r\n\r\n## 5. Hybrid of 3 & 4\r\n\r\n```ts\r\ntype LineData = CharData[]\r\n\r\n// [0]: The character\r\n// [1]: The width\r\ntype CharData = [string, number];\r\n\r\nclass CharAttributes {\r\n  private _data: Int32Array;\r\n\r\n  // Getters pull data from _data (woo encapsulation!)\r\n  public get flags(): number;\r\n  public get truecolorBg(): number;\r\n  public get truecolorFg(): number;\r\n}\r\n\r\ninterface CharAttributeEntry {\r\n  attributes: CharAttributes,\r\n  start: [number, number],\r\n  end: [number, number]\r\n}\r\n\r\nclass Buffer extends CircularList<LineData> {\r\n  // Sorted list since items are almost always pushed to end\r\n  private _attributes: CharAttributeEntry[];\r\n  private _attributeCache: ICharAttributeCache;\r\n\r\n  public getAttributesForRows(start: number, end: number): CharAttributeEntry[] {\r\n    // Binary search _attributes and return all visible CharAttributeEntry's to\r\n    // be applied by the renderer\r\n  }\r\n}\r\n\r\ninterface ICharAttributeCache {\r\n  // Never construct duplicate CharAttributes, figuring how the best way to\r\n  // access both in the best and worst case is the tricky part here\r\n  getAttributes(flags: number, fg: number, bg: number): CharAttributes;\r\n}\r\n```\r\n\r\n**Pros**\r\n\r\n- Protentially the fastest and most memory efficient\r\n- Very memory efficient when the buffer contains many blocks with styles but only from a few styles (the common case)\r\n- Encapsulates the complexity of storing the data inside an array (`.flags` instead of `[0]`)\r\n\r\n**Cons**\r\n\r\n- More complex than the other solutions, it may not be worth including the cache if we already keep a single `CharAttributes` per block?\r\n- Extra overhead in `CharAttributeEntry` object\r\n- Changing attributes of a range of characters inside another range is more complex\r\n\r\n## 6. Hybrid of 2 & 3\r\n\r\nThis takes the solution of 3 but also adds in a lazily evaluates text string for fast access to the line text. Since we're also storing the characters in `CharData` we can lazily evaluate it.\r\n\r\n```ts\r\ntype LineData = {\r\n  text: string,\r\n  CharData[]\r\n}\r\n\r\n// [0]: The character\r\n// [1]: The width\r\ntype CharData = [string, number];\r\n\r\nclass CharAttributes {\r\n  public readonly _start: [number, number];\r\n  public readonly _end: [number, number];\r\n  private _data: Int32Array;\r\n\r\n  // Getters pull data from _data (woo encapsulation!)\r\n  public get flags(): number;\r\n  public get truecolorBg(): number;\r\n  public get truecolorFg(): number;\r\n}\r\n\r\nclass Buffer extends CircularList<LineData> {\r\n  // Sorted list since items are almost always pushed to end\r\n  private _attributes: CharAttributes[];\r\n\r\n  public getAttributesForRows(start: number, end: number): CharAttributes[] {\r\n    // Binary search _attributes and return all visible CharAttributes to be\r\n    // applied by the renderer\r\n  }\r\n\r\n  // If we construct the line, hang onto it\r\n  public getLineText(line: number): string;\r\n}\r\n```\r\n\r\n**Pros**\r\n\r\n- Lower memory than today even though we're also storing truecolor data\r\n- Can optimize application of attributes, rather than checking every single character's attribute and diffing it to the one before\r\n- Encapsulates the complexity of storing the data inside an array (`.flags` instead of `[0]`)\r\n- Faster access to the actual line string\r\n\r\n**Cons**\r\n\r\n- Extra memory due to hanging onto line strings\r\n- Changing attributes of a range of characters inside another range is more complex\r\n\r\n## Solutions that won't work\r\n\r\n- Storing the string as an int inside an `Int32Array` will not work as it takes far to long to convert the int back to a character."},"comment":{"url":"https://api.github.com/repos/xtermjs/xterm.js/issues/comments/407471263","html_url":"https://github.com/xtermjs/xterm.js/issues/791#issuecomment-407471263","issue_url":"https://api.github.com/repos/xtermjs/xterm.js/issues/791","id":407471263,"node_id":"MDEyOklzc3VlQ29tbWVudDQwNzQ3MTI2Mw==","user":{"login":"jerch","id":6193135,"node_id":"MDQ6VXNlcjYxOTMxMzU=","avatar_url":"https://avatars0.githubusercontent.com/u/6193135?v=4","gravatar_id":"","url":"https://api.github.com/users/jerch","html_url":"https://github.com/jerch","followers_url":"https://api.github.com/users/jerch/followers","following_url":"https://api.github.com/users/jerch/following{/other_user}","gists_url":"https://api.github.com/users/jerch/gists{/gist_id}","starred_url":"https://api.github.com/users/jerch/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jerch/subscriptions","organizations_url":"https://api.github.com/users/jerch/orgs","repos_url":"https://api.github.com/users/jerch/repos","events_url":"https://api.github.com/users/jerch/events{/privacy}","received_events_url":"https://api.github.com/users/jerch/received_events","type":"User","site_admin":false},"created_at":"2018-07-24T16:36:53Z","updated_at":"2018-07-24T16:36:53Z","author_association":"CONTRIBUTOR","body":"@Tyriar I did some further tests with rust for webassembly usage and rewrote the parser. Note that my rust skills are abit \"rusty\" since I did not get yet deeper into it, therefore the following might be the result of weak rust code. Results:\r\n\r\n- The data handling within the wasm part is slightly faster (5 - 10%).\r\n- Calls from JS into wasm create some overhead and eats all the benefits from above. In fact it was ~20% slower.\r\n- The \"binary\" will be smaller than the JS counterpart (not really measured since I did not implement all stuff).\r\n- To get JS <--> wasm transition easily done some bloatcode is needed to handle the JS types (only did the string translation).\r\n- We cannot avoid JS to wasm translation since the browser DOM and events are not accessible there. It could only be used for core parts, which are not that performance critical anymore (beside the mem consumption).\r\n\r\nUnless we want to rewrite the whole core libs in rust (or any other wasm capable language) we cannot gain anything from moving to a wasm lang imho. A plus of nowadays wasm langs is the fact that most support explicit memory handling (could help us with the buffer problem), downsides are the introduction of a totally different language into a primarily TS/JS focused project (a great barrier for code additions) and the translation costs between wasm and JS land.\r\n\r\n**TL;DR**\r\nxterm.js is to broadly into general JS stuff like DOM and events to gain anything from webassembly even for a rewrite of the core parts."}}
{"actor":{"display_login":"jerch"}}