3 ms·

I only partially understand this article but this seems incredibly relevant to me since I'm planning on writing a spreadsheet engine in rust. Cell values requir

I only partially understand this article but this seems incredibly relevant to me since I'm planning on writing a spreadsheet engine in rust. Cell values require me to have something like (this very poorly written POC code, sorry): pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box<Expr>, char, Box<Expr>), Function(String, Vec<Expr>), } I'll keep reading and studying! If anyone has more resources to throw at me, I'm all ears

hathawsh 3y ago
Sounds like a fun project. If it's intended for ordinary users, one thing you should expect them to do is add content to the 4 extreme corners of a sheet and see if the spreadsheet engine falls over as a result. If you allow 1 million by 1 million cells, and you store a "null" for every cell not filled in, then the engine will run out of memory. That means you might consider storing the cell content in a sparse manner. One way to do that is with a hash map implementation such as "hashbrown". Just a thought. (To clarify why I'm bringing this up, the points in this article are low level details that you probably don't need to think about if you start with a hash map and thereby avoid running into memory constraints initially.)
- airstrike 3y ago
  Thanks, great point indeed. I am looking into this https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown The way I think about it -- rather naively, I suppose -- is that I care more about the references cells make to each other than the actual grid of cells displayed on a table. The latter feels more like a "view" of the data than an actual data structure? This also seems to align with the relative priority of (sorted from highest to lowest): figuring out the order of evaluation, calculating those evaluations, and finally displaying the results of the evaluation
vlovich123 3y ago
The problem being highlighted is that if you have widely disparate sizes of the variants and/or a lot of these in an array, your hurting performance because there’s a lot of space being wasted on padding. A common technique that came from gaming is that if you have an array of structs (AoS) (eg array<struct { health: int, ammo: Ammo, … }> to break it up into a struct of arrays (SoA): struct Humans { healths: Vec<int>, ammo: Vec<ammo>, … }. Then the ith index into those vecs is the ith Human in the AoS layout (parallel vecs here are for example, but it’s not optimally efficient because the bookkeeping of length and capacity on a per field basis is wasteful as that info is duplicate). This is basically a similar idea except for enums and doing it automatically in a way that Rust can’t. It’s possible the problem is a bit overrated in terms of how big of a problem this is. Also, in Rust you may be able to wrap the third party type in your own and then the derive macro approach probably can work. Re your spreadsheet, just keep in mind of this as a possible optimization and you have to first figure out if you’re building for speed (ie you’ve done this a few times and you know this is probably a bottleneck) or experience (ie build for simplicity and understanding)
- rudedogg 3y ago
  On the subject of AoS, Zig has a cool data structure for that: https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-in-userland-40m0 https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-i...
- airstrike 3y ago
  Thank you -- definitely building it for speed which is why this felt topical. I really appreciate your explanation, it's super clear.
nhatcher 3y ago
Hey, I've actually build a spreadsheet engine in Rust. Not open sourced, but could give you some pointers. You are going to hit lots of performance issues before you can have some gains using the methods of the article. The single most difficult problem is the evaluation strategy.
- airstrike 3y ago
  Hey, thanks for the offer. I have been thinking about evaluation and the extent of my strategy so far has been to consider it as a dependency graph, which led me to this interesting article: https://hyperformula.handsontable.com/guide/dependency-graph.htm https://hyperformula.handsontable.com/guide/dependency-graph... Also it sounds like the right next step for me is to read more on incremental computation. Someone on reddit just pointed me to adapton: https://docs.rs/adapton/latest/adapton/ https://docs.rs/adapton/latest/adapton/ Actually implementing anything with Rust is on my TODO list (I'm spending some time on the UI prototype right now) I will give a couple things a try and then, if you don't mind, I can ping you via email. I was checking out your website and loved the read on the parser -- not to mention A MAZE (played all the way to level 4!)
  - nhatcher 3y ago
    Wow! Glad you had a look around. Yes, please send me an email whenever you feel like. And yes, you are going to need some sort of "support graph" and topological sorting. But this is way more complicated than it looks like. Most functions in a spreadsheet don't know it's dependencies until you are actually computing them, like `LOOKUP` or `IF`. Some functions like `RANDBETWEEN` or `NOW` change their value every time. In some modern spreadsheets some functions like `SORT` or `UNIQUE` spill their values to some other cells. Calculating dependencies correctly in all those situations can be challenging. There is not a lot of literature on spreadsheet implementation and reading code of existing open source implementations is hard. And exception is Peter Sesoft: https://mitpress.mit.edu/9780262526647/spreadsheet-implementation-technology/ https://mitpress.mit.edu/9780262526647/spreadsheet-implement... and https://www.itu.dk/people/sestoft/funcalc/ https://www.itu.dk/people/sestoft/funcalc/ My recommendation would be to first set the scope. Then code manually the lexer and parser and drawn those two in tests. Excel formulas can be quite complicated! There are lots of fancy things you can do there like use arena allocators and other optimizations. I would try to avoid that on a first go. Here is something that I have found extremely convenient. Excel saves the cell formula AND the resulting value. Meaning that to create a test case you just need to create an Excel workbook (and a xlsx parser, of course). Doing the UI for a spreadsheet is an equally challenging problem. Good luck!!!! Oh, and remember this thread from a couple of days ago. Might be inspiring: https://news.ycombinator.com/item?id=37527720 https://news.ycombinator.com/item?id=37527720

hathawsh 3y ago

Sounds like a fun project. If it's intended for ordinary users, one thing you should expect them to do is add content to the 4 extreme corners of a sheet and see if the spreadsheet engine falls over as a result. If you allow 1 million by 1 million cells, and you store a "null" for every cell not filled in, then the engine will run out of memory. That means you might consider storing the cell content in a sparse manner. One way to do that is with a hash map implementation such as "hashbrown". Just a thought. (To clarify why I'm bringing this up, the points in this article are low level details that you probably don't need to think about if you start with a hash map and thereby avoid running into memory constraints initially.)

airstrike 3y ago
Thanks, great point indeed. I am looking into this https://github.com/rust-lang/hashbrown https://github.com/rust-lang/hashbrown The way I think about it -- rather naively, I suppose -- is that I care more about the references cells make to each other than the actual grid of cells displayed on a table. The latter feels more like a "view" of the data than an actual data structure? This also seems to align with the relative priority of (sorted from highest to lowest): figuring out the order of evaluation, calculating those evaluations, and finally displaying the results of the evaluation

vlovich123 3y ago

The problem being highlighted is that if you have widely disparate sizes of the variants and/or a lot of these in an array, your hurting performance because there’s a lot of space being wasted on padding. A common technique that came from gaming is that if you have an array of structs (AoS) (eg array<struct { health: int, ammo: Ammo, … }> to break it up into a struct of arrays (SoA): struct Humans { healths: Vec<int>, ammo: Vec<ammo>, … }. Then the ith index into those vecs is the ith Human in the AoS layout (parallel vecs here are for example, but it’s not optimally efficient because the bookkeeping of length and capacity on a per field basis is wasteful as that info is duplicate). This is basically a similar idea except for enums and doing it automatically in a way that Rust can’t. It’s possible the problem is a bit overrated in terms of how big of a problem this is. Also, in Rust you may be able to wrap the third party type in your own and then the derive macro approach probably can work. Re your spreadsheet, just keep in mind of this as a possible optimization and you have to first figure out if you’re building for speed (ie you’ve done this a few times and you know this is probably a bottleneck) or experience (ie build for simplicity and understanding)

rudedogg 3y ago
On the subject of AoS, Zig has a cool data structure for that: https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-in-userland-40m0 https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-i...
airstrike 3y ago
Thank you -- definitely building it for speed which is why this felt topical. I really appreciate your explanation, it's super clear.

nhatcher 3y ago

Hey, I've actually build a spreadsheet engine in Rust. Not open sourced, but could give you some pointers. You are going to hit lots of performance issues before you can have some gains using the methods of the article. The single most difficult problem is the evaluation strategy.

airstrike 3y ago
Hey, thanks for the offer. I have been thinking about evaluation and the extent of my strategy so far has been to consider it as a dependency graph, which led me to this interesting article: https://hyperformula.handsontable.com/guide/dependency-graph.htm https://hyperformula.handsontable.com/guide/dependency-graph... Also it sounds like the right next step for me is to read more on incremental computation. Someone on reddit just pointed me to adapton: https://docs.rs/adapton/latest/adapton/ https://docs.rs/adapton/latest/adapton/ Actually implementing anything with Rust is on my TODO list (I'm spending some time on the UI prototype right now) I will give a couple things a try and then, if you don't mind, I can ping you via email. I was checking out your website and loved the read on the parser -- not to mention A MAZE (played all the way to level 4!)
- nhatcher 3y ago
  Wow! Glad you had a look around. Yes, please send me an email whenever you feel like. And yes, you are going to need some sort of "support graph" and topological sorting. But this is way more complicated than it looks like. Most functions in a spreadsheet don't know it's dependencies until you are actually computing them, like `LOOKUP` or `IF`. Some functions like `RANDBETWEEN` or `NOW` change their value every time. In some modern spreadsheets some functions like `SORT` or `UNIQUE` spill their values to some other cells. Calculating dependencies correctly in all those situations can be challenging. There is not a lot of literature on spreadsheet implementation and reading code of existing open source implementations is hard. And exception is Peter Sesoft: https://mitpress.mit.edu/9780262526647/spreadsheet-implementation-technology/ https://mitpress.mit.edu/9780262526647/spreadsheet-implement... and https://www.itu.dk/people/sestoft/funcalc/ https://www.itu.dk/people/sestoft/funcalc/ My recommendation would be to first set the scope. Then code manually the lexer and parser and drawn those two in tests. Excel formulas can be quite complicated! There are lots of fancy things you can do there like use arena allocators and other optimizations. I would try to avoid that on a first go. Here is something that I have found extremely convenient. Excel saves the cell formula AND the resulting value. Meaning that to create a test case you just need to create an Excel workbook (and a xlsx parser, of course). Doing the UI for a spreadsheet is an equally challenging problem. Good luck!!!! Oh, and remember this thread from a couple of days ago. Might be inspiring: https://news.ycombinator.com/item?id=37527720 https://news.ycombinator.com/item?id=37527720