5 ms·
So one of the applications I have worked with was an embedded credit card terminal app which needed a transactional database. Since I could not find a product t
by lmilcin 6y ago
So one of the applications I have worked with was an embedded credit card terminal app which needed a transactional database. Since I could not find a product that would fit all requirements I decided to write one.
Now, you can imagine smart algorithms, trees, hashes...
Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all its updates. No indexes. Some algorithms were plainly O(n^3).
Yeah, I got into many heated discussions with "computer scientists" in the team. Yet for all their might they were not able to improve upon the program because they forget that algorithmic complexity is only one factor of performance.
Because I used extremely simple algorithms (like linear search) the operations were very simple and progressed quite fast on a CPU that was good at prefetching from the storage.
The total amount of memory available was just 0,5MB meaning that the "super inefficient" scans still completed within perception threshold of the user.
While O(n^3) was used for some operations, the application state machine which limited number of actual number of steps. Most transactions follow same basic pattern of execution and so I don't care what happens when somebody does 500 updates to the transaction when I can figure out there will ever be 5 state changes at most.
There were other consideration for the program. For example, it had to use very little instructions (we were very short on space) and it had to work in constant memory (to be able to statically calculate stack space necessary, for example).
- wkz 6y agoA clear case of Rob Pike’s 3rd rule of programming: https://users.ece.utexas.edu/~adnan/pike.html https://users.ece.utexas.edu/~adnan/pike.html
- WoodenChair 6y agoIt's a great anecdote that shows why we shouldn't ONLY worry about the CS side, but it doesn't mean the system wouldn't have been even more robust/faster/more scalable using better data structures/algorithms. Just because doing the simplest darn thing gets the job done, doesn't mean it's the best way to do it. Obviously you chose this solution because it made the most sense given your constraints (time/money/knowledge/microcontroller limitations). But that doesn't mean it was an optimal solution nor that with slightly more time/money/knowledge a significantly better solution couldn't have been found.
- leeter 6y agoPeople forget that Big O is only part of the story, they also need to consider Little o and average runtime. Just because something is n^2 or worse asymptotically doesn't mean the average runtime will be that bad. There are many cases where the average runtime is closer to Little o almost all the time.
- zimpenfish 6y ago> they also need to consider Little o and average runtime. Frequency of run is also important - a batch job that takes 5 hours that only runs once a month? Is it worth optimising that?
- ric2b 6y agoAverage is useful but is Little o relevant outside of very low latency things like games? If the input is small it will run fast for any solution anyway.
- lmilcin 6y agoWhy would efficiency be relevant only for low latency things?
- zimpenfish 6y ago> I got into many heated discussions with "computer scientists" in the team. Had a week long argument once about an (relatively) inefficient MySQL query because "it's not going to work for 1000 things" when a) we had barely 10 things currently running and b) the customer was >this far< from cancelling because stuff wasn't working (which this query would help with.) It was a frustrating time. I think there's a lot of developers who "know the price of everything and the value of nothing".