Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

14,000x Speedup (2015)

james.hiebert.name

Post reply on HN
Print view View original

151–160 of 237 posts

Re: 14,000x Speedup (2015)

#151

Post by thangalin »

chrismorgan wrote: post #135

Point of document implementation: please don’t use … for equations, or else the equations are simply missing in environments where MathJax doesn’t run (e.g. JS disabled, text mode browser, or JS fails to load—all up, it’s more common than you realise). Use a form of markup that will fail visible rather than fail invisible . TeX mathematics notation is far better than a void. You could make this abuse of a bit more to…

> please don’t use … for equations

KeenWrite[0], my desktop text editor, has an Export HTML using TeX/SVG feature that encodes math glyphs as vector paths, embedding the SVG into the resulting HTML file.

On the subject of optimizations, KeenWrite can render 1,000 simple TeX formulas to SVG format in about 500 milliseconds (on my desktop machine), sufficient for real-time previews. Two libraries needed changes to accomplish this feat.

First, JFreeSVG and Apache Batik both suffer from the same performance problem: they use Java's NumberFormat to convert floating point numbers to strings. It's slow because of internationalization rules, which aren't necessary for a machine-readable format. The fix entailed replacing NumberFormat with the Ryū algorithm[1].

Second, JMathTeX[2] was parsing TeX by throwing exceptions for flow control. In Java, throwing an exception forces the virtual machine to fill out a stack trace. Normally this wouldn't result in abysmal performance, but the flow control was being executed for each character in every macro name encountered. Pre-parsing macro names without any flow control resolved the issue.

Further optimizations were made, but those two were the lion's share. Combined, the total time went from 1 TeX formula to SVG format in ~5 seconds to 1,000 in ~.5 seconds.

[0]: https://github.com/DaveJarvis/keenwrite

[1]: https://github.com/DaveJarvis/JMathTeX

[2]: http://jmathtex.sourceforge.net

Re: 14,000x Speedup (2015)

#152

Post by arethuza »

hinkley wrote: post #144
mynegation wrote: post #39

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each…

I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are d…

Out of interest, did they say what they thought the hardest part of programming is?

Re: 14,000x Speedup (2015)

#153

Post by leeter »

lmilcin wrote: post #56
dumbfounder wrote: post #16

Computer Science for the... loss? I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US…

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…

People 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.

Re: 14,000x Speedup (2015)

#154

Post by fzimmermann »

I see some issues with the problem description and the solution: The author assumes the problem can be split in x and y independently. Firstly, this has not to be true for all projections and grids. Secondly, the solution minimizes Manhattan distance in lat/long., not actual distance (you can construct points where the minima are different). This will not matter if you can approximate both grids as regular (equidistant and rectangular grids). But in that case, you could easily calculate for each point in one grid the corrosponding point in the other grid by scaling and rounding...

Re: 14,000x Speedup (2015)

#155

Post by godelski »

vidarh wrote: post #111
neves wrote: post #58

Earlier quoted context omitted.

This is a usual problem with C++ and why I hate it. There's a lot going on under the hoods, and you must be really knowledgeable of the language to prevent stupid things. Following some idioms you can really avoid it, but it is useless since your coworkers will fall into the language traps.

Knowing if you're copying or passing references is essential to understanding most languages that supports both. It's scary how many people are unaware of it, though. Not nearly as dramatic as the example above, but I once cut the time spent on page generation for a commercial CMS by 30% my first day in a new job by realising they did excessive new allocation of strings instead of concatenation (which will amortise t…

One thing I tell people is that beginning a good C/C++ programmer made me a much better python programmer and makes it substantially easier to pick up other languages. It's not so specific to the language being C as much as it is learning about memory and the what you learn by constantly shooting yourself in the foot because you make dumb mistakes (I still think mistakes are the best way to learn).

Re: 14,000x Speedup (2015)

#156

Post by stouset »

mesarvagya wrote: post #142
8ytecoder wrote: post #134

Earlier quoted context omitted.

This is at the very least a clever and involved optimization. Let me tell you the story of my similar 10h to 10min fix. We had this cronjob that was supposed to run every hour, detect all changes to the customers and related table and sync with the marketing saas tool. It was written in Rails and took 10 mins at first. As we grew the time taken by this job also grew linearly. To a point where it took 10 hours and we…

Sounds like classic n+1 problem

Or more likely, the classic “fetch an entire table from the database and work on it locally” problem that seems endemic in code written by people who don’t understand the capabilities of SQL.

Works great in dev with a local sqlite instance and ten rows. Not so great in prod.

Re: 14,000x Speedup (2015)

#157

Post by mynegation »

arethuza wrote: post #152
hinkley wrote: post #144

Earlier quoted context omitted.

I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are d…

Out of interest, did they say what they thought the hardest part of programming is?

Just one hardest part? Could be naming things and off by one errors.

Re: 14,000x Speedup (2015)

#158

Post by [deleted] »

chrismorgan wrote: post #135

Point of document implementation: please don’t use … for equations, or else the equations are simply missing in environments where MathJax doesn’t run (e.g. JS disabled, text mode browser, or JS fails to load—all up, it’s more common than you realise). Use a form of markup that will fail visible rather than fail invisible . TeX mathematics notation is far better than a void. You could make this abuse of a bit more to…

[deleted]

Re: 14,000x Speedup (2015)

#159

Post by hinkley »

I think I've related this before, but one of my favorite bug reports, and the most interesting Order of Complexity I've ever documented was one I filed for TogetherJ.

Well before anyone coined the term 'monorepo' we had built one, and the architect and some of the leads noticed that each time we added another module to a TogetherJ project, the time to open the project shot way, way up.

I got on the case, and determined that with about 80% of our project loaded it took 28 hours to open the project. At this point I reported it to Together, and they said it was something to do with scanning the data for each module and the workaround was to keep all the data at the monorepo level. That got the load time back down to 20 minutes (less if you ejected some of the less interesting modules from the project). They also fixed the problem in the next release.

About this time I actually sat down and plotted the trend line, it fell almost exactly on an O(n^5) curve. I've seen n!, I've seen x^n loads, but I don't think I've ever seen n^5 before or since.

Re: 14,000x Speedup (2015)

#160

Post by rgossiaux »

jdmichal wrote: post #62
colejohnson66 wrote: post #48

Earlier quoted context omitted.

It’s good to understand what the “Big O” for your algorithm is, but, yes, people who obsess over it are annoying. If I know I’m processing 100 items very rarely,[a] does it matter if my quick and dirty sorting (no pun intended) algorithm is bubble or quick sort? They both complete in a fraction of a second, and the user (generally) isn’t going to notice a difference between a single frame update delta or two. [a] Key…

My rule is that the only sort I will ever write by hand is a bubble sort. It's basically impossible to write incorrectly. If and when that breaks performance, then I will bring in an external sorting library and figure out what works the best for the data. It's the equivalent philosophy to always buying the cheapest tool you can the first time around. When you break that tool, then you go out and buy the expensive on…

The cheapest tool you can find is surely the sort in your programming language's standard library. Writing your own sort seems crazy to me.
Post reply on HN