r/Python • • Jan 01 '20

"The rules of perf" at Dropbox

Post image
1.6k Upvotes

162 comments sorted by

137

u/ZombieRandySavage Jan 02 '20

TL;DR. Really wish we hadn’t written the core application of our business in Python.

47

u/notsohipsterithink Jan 02 '20

Dropbox still uses Python extensively. It’s only in case things don’t scale and you have no other choice, don’t use Python.

Python is great for developer productivity and iterating quickly. Dropbox actually loves python, they have a blog post about it.

0

u/stefantalpalaru Jan 02 '20

Python is great for developer productivity and iterating quickly. Dropbox actually loves python

Is that why they wasted 3 years porting a quarter of their code base to Python3, after hiring the language creator?

1

u/NoahTheDuke Jan 02 '20

What was wasted about it?

-1

u/stefantalpalaru Jan 02 '20

What was wasted about it?

Time and human resources.

1

u/notsohipsterithink Jan 02 '20

They hired Guido to work on conflict resolution algorithms, not Python.

It wasn’t a waste for them. See the blog posts in the comment above.

-3

u/stefantalpalaru Jan 02 '20

They hired Guido to work on conflict resolution algorithms, not Python.

Bullshit. Guido ended up coding a tool to "insert annotations into your source code based on call arguments and return types observed at runtime" - https://github.com/dropbox/pyannotate

That was obviously used to help port Python2 to Python3, but I'm curious why did you think they hired the Python language creator - a notoriously mediocre programmer who's still unable to understand functional programming - to work on something that's not Python code?

1

u/notsohipsterithink Jan 03 '20

Guido obviously did a lot for Dropbox in his 6-year tenure there. But the python language itself wasn’t his initial focus:

https://blogs.dropbox.com/developers/2013/07/how-the-datastore-api-handles-conflicts-part-1-basics-of-offline-conflict-handling/

As far as your other comments, here’s a little gem for you —

https://blog.dropbox.com/topics/company/thank-you--guido

“What I love about Python is it just works,” says Houston. “It is so intuitive and beautifully designed. A lot of these attributes inspired my co-founder Arash and me when we thought about the design ethos for Dropbox.”

0

u/stefantalpalaru Jan 03 '20

It is so intuitive and beautifully designed

Nothing says "intuitive" and "beautifully designed" like hidden state (and hidden pass-by-reference) for some of the builtin types: https://docs.python-guide.org/writing/gotchas/#mutable-default-arguments

1

u/notsohipsterithink Jan 03 '20

That is actually a pretty small list of gotchas and I’ve personally never had issues with any of these in production. PyCharm actually warns you against using mutable objects as defaults.

Every language has its gotchas. This is a very small and harmless list compared to many other popular languages.

-1

u/stefantalpalaru Jan 03 '20

gotchas

Design failures.

4

u/solidiquis1 Jan 02 '20

Could we get a link to that blog post?

5

u/eskermo Jan 02 '20

Not OP, but I didn't find a blog post about Dropbox loving Python, just that it's used extensively by their team in a couple of articles: https://blogs.dropbox.com/tech/2018/09/how-we-rolled-out-one-of-the-largest-python-3-migrations-ever/ and https://blogs.dropbox.com/tech/2019/09/our-journey-to-type-checking-4-million-lines-of-python/.

2

u/solidiquis1 Jan 02 '20

Thanks m8!

1

u/notsohipsterithink Jan 02 '20

Yep, there was a much older one but the ones you posted are better.

3

u/malicart Jan 02 '20

Simply google "Dropbox python post" and read it for yourself.

29

u/c_o_r_b_a Jan 02 '20

It's saying the opposite, though. Only issues where those first 4 steps fail need to be rewritten, which is a much, much smaller subset of their entire codebase.

Python is likely what got them off the ground so quickly and probably directly led to their success. See also: reddit, Instagram

4

u/stefantalpalaru Jan 02 '20

Python is likely what got them off the ground so quickly and probably directly led to their success. See also: reddit

Reddit was originally written in Common Lisp.

1

u/F0064R Jan 02 '20

Okay, but they also ripped it out for a reason

0

u/stefantalpalaru Jan 02 '20

they also ripped it out for a reason

Yes, they needed to dumb it down in order to increase the number of cheap programmers to choose from.

2

u/F0064R Jan 02 '20

Yup, smart move from a product manager’s perspective

-1

u/c_o_r_b_a Jan 02 '20

Yes, and it failed to get off the ground as a result. Once they switched to Python, things started growing. If they had never made the switch early on, it's very unlikely we'd be having this discussion here right now.

1

u/mipadi Jan 03 '20

Reddit was rewritten in Python very early in its lifetime, less than a year after it debuted, and it was rewritten in Python because of a lack of choice in libraries. The use of Lisp wasn't hindering its growth, and the rewrite occurred so early that it's not possible to say whether it would have hindered Reddit's growth or not.

1

u/c_o_r_b_a Jan 03 '20

The reddit co-founders described other friction with Lisp as well, in interviews. I imagine they would agree it's a lot less likely it would have grown to popularity if they had stuck with Lisp.

Also, Aaron Swartz said this about it:

(Disclosure: We used my web.py library.) The others knew Lisp (they wrote their whole site in it) and they knew Python (they rewrote their whole site in it) and yet they decided they liked Python better for this project. The Python version had less code that ran faster and was far easier to read and maintain.

12

u/ukralibre Jan 02 '20

Why?

57

u/ZombieRandySavage Jan 02 '20

Because it scales poorly to large applications. Go try and refactor a suitably large project, it’s impossible.

Don’t worry there are terrible parts to every language. They didn’t have time to make a clever poster for C++ because they are still trying to understand the super clever template code someone wrote.

17

u/[deleted] Jan 02 '20 edited Jan 02 '20

You could transpile Python to C or C++.

You could write the performance-intensive functions in C or C++, or even assembly if you're a sociopath, and then call them from Python.

I'm not arguing that these techniques provide equal or even comparable performance to writing your whole library in native low-level code. But Python is actually higher on the TIOBE index than both C++ and C#, and of course it's way higher than assembly. This might reflect a fundamental tradeoff: the greater availability of Python developers may mean that it's easier to hire a robust dev team who can develop and debug in Python than in the other languages, so faster iteration. That is - the theoretically achievable performance in certain languages must be viewed through the lens of practically achievable performance based on the availability (and affordability!) of suitable developers.

Finally - within a certain range, lower-performing code can be solved, crudely but effectively, by buying more compute. But good code cannot be developed or debugged faster by buying more developers (see The Mythical Man-Month).

2

u/ZombieRandySavage Jan 02 '20

Yep, you can do that.

1

u/not_perfect_yet Jan 02 '20

You could write the performance-intensive functions in C or C++, or even assembly if you're a sociopath, and then call them from Python.

...I knew about C, but not about assembly. That's pretty wild, now I have to try it.

0

u/stefantalpalaru Jan 02 '20

You could transpile Python to C or C++.

Just a subset of it. Look at Cython.

0

u/[deleted] Jan 02 '20

how does such dumb, misinformed drivel get upvoted on this sub? you have no idea what you're talking about.

-1

u/ZombieRandySavage Jan 02 '20

Nice rebuttal dummy.

0

u/[deleted] Jan 02 '20

[deleted]

11

u/notsohipsterithink Jan 02 '20

Some languages naturally lend themselves to having large or convoluted codebases. Like C++ or Java.

11

u/jambox888 Jan 02 '20

Do you mean Java is better suited to large codebases or that it tends to produce them?

10

u/[deleted] Jan 02 '20

Both would apply IMO

1

u/jambox888 Jan 02 '20

That's a bit of a chicken and egg paradox IMHO. It's probably easier to structure a large project in Java than C++ but that isn't saying much.

5

u/notsohipsterithink Jan 02 '20

Java tends to produce large codebases.

The lack of a proper module system (until Java 9 which very few have adopted) meant JAR clusterfuck and forced most codebases to become huge monoliths.

Production Python (or Go) codebases are usually microservices. But they can be monolithic easily too.

2

u/Smallpaul Jan 02 '20

I’ve never programmed Java seriously. What do you mean by it lacking a module system? Isn’t it similar to Python with dotted paths etc.?

2

u/jambox888 Jan 02 '20

Modules <> packages. See here. I don't really understand why they say the lack of a module system tends to produce monoliths though, monoliths were just the standard application style back then. There was never anything stopping people writing microservices afaik. Unless there were issues with reuse.

3

u/Smallpaul Jan 02 '20

So what Python calls modules, java calls packages and vice versa. Great!

1

u/notsohipsterithink Jan 02 '20

There was nothing technically stopping people from writing microservices. However, the fact that you had to import the whole massive JAR even when you needed only a single function, made developers more biased towards monoliths.

→ More replies (0)

1

u/notsohipsterithink Jan 02 '20

Project Jigsaw (introduced in Java 9) gives Java a module system similar to Python. More info here:

https://openjdk.java.net/projects/jigsaw/

From the overview, these are the advantages of modules over classpaths:

As described in the JSR, the specific goals of the module system are to provide:

— Reliable configuration, to replace the brittle, error-prone class-path mechanism with a means for program components to declare explicit dependences upon one another, along with

— Strong encapsulation, to allow a component to declare which of its public types are accessible to other components, and which are not.

20

u/G3n3r0 Jan 02 '20

With a good IDE (i.e. Visual Studio/CLion, most of the annoying grunt work (e.g. changing function signatures, etc.) should happen nearly automatically. Python can sometimes get close to that maybe, unless people did clever things with dynamic dispatch or getattr overloading in which case you're fucked.

5

u/[deleted] Jan 02 '20

It really helps to add type annotation, of course the clever stuff will bite, unless you can express the type correctly.

1

u/ZombieRandySavage Jan 02 '20

I think ones just objectively more difficult than the other. Just easier to refactor statically typed stuff.

0

u/[deleted] Jan 02 '20

[deleted]

10

u/[deleted] Jan 02 '20

Try using type annotations, if you have IDE that understands them out makes programming quite enjoyable.

0

u/[deleted] Jan 02 '20

[deleted]

6

u/[deleted] Jan 02 '20

You can still add the annotations.

0

u/[deleted] Jan 02 '20

[deleted]

6

u/[deleted] Jan 02 '20

I added it in code that I changed, other people started liking that autocomplete was working and started adding annotations themselves as well. It helps a lot with a large code base.

9

u/nocipher Jan 02 '20

Python is strongly typed. You probably meant statically typed. C++ is actually weakly typed.

6

u/e_falk Jan 02 '20

Python tends to not be as performant as is necessary for companies that work at similar scales to Dropbox

Source: company I work at works at comparable scales and python’s problems with concurrency with regards to the GIL /really/ starts to rear it’s ugly head in that environment

17

u/jambox888 Jan 02 '20

Why? You have a bunch of servers handling requests, it's not like you have a single runtime that's trying to do multithreading.

I mean god help you if you do.

The whole point of scalable web design is to be stateless and abstract out the data store into its own tier.

2

u/[deleted] Jan 02 '20

There are practical limits to how much hardware you can throw at a problem and how much you gain with every additional unit of horizontal scaling.

2

u/jambox888 Jan 02 '20

maybe we're thinking of different problem domains then but for a web service there literally aren't limits. if there were, google or yt wouldn't exist.

1

u/[deleted] Jan 02 '20

Read my post again.

I never claimed absolute limits, although there are in a lot of cases, I said there are practical limits (money is ome) and pointed out to the issues like diminishing returns when scaling out horizontally (that then augment such practical limits to scaling).

99

u/ketralnis Jan 02 '20

Not really, my company uses Python by default and only ports stuff out when it’s not fast enough. It’s usually fast enough, the performance critical stuff is a tiny fraction of your code. If you can be more productive the rest of the time, you’re still ahead.

31

u/ZombieRandySavage Jan 02 '20

Yep, but losing the ability to refactor large code bases significantly hampers their longevity. There are ways around it as well.

Honestly I don’t know if performance is really the issue. There are plenty of generalized libraries for getting large computation done quickly. It’s really maintenance in my mind.

13

u/MyreMyalar Jan 02 '20

I don't understand what problem you have with refactoring python code. As long as you make use of type hints (which you should be in a large code base with many developers anyway) it seems to work pretty much like any other programming language.

10

u/Pitirus Jan 02 '20

That is true but keep in mind that typings in python (as we have them now) were introduced in 3.5 (so 2015) and I would assume from my own experience that they haven't been widely used in large codebases until at least introduction of 3.6 (add to this that in prod code you probably don't want to switch right after the release).

All of this would mean that dropbox probably had to introduce some standard of their own (which is painful for new devs) and might have not yet switched to the current official standard for most parts of their code.

1

u/stefantalpalaru Jan 02 '20

typings in python (as we have them now) were introduced in 3.5

No, they were introduced long ago, for Python2: https://mypy.readthedocs.io/en/stable/python2.html

1

u/Pitirus Jan 02 '20

The module this link is referencing was created for python 3.5 (and 2.7 for compatibility) in 2015 as separate package which became part of the standard library with release of 3.6

Edit: ok you mean mypy itself, but still that's only optional and according to it's about page it's from 2012 so already python 3 was out a long time

0

u/stefantalpalaru Jan 02 '20

ok you mean mypy itself, but still that's only optional

There is no other way to check Python2 or Python3's partial typing than with mypy - an external tool.

4

u/MyreMyalar Jan 02 '20

No criticism of Dropbox intended, I was just replying to the chap above who seemed not to be aware that refactoring has been working perfectly well (at least in my experience) in python for several years now.

As an argument for not using fairly old versions of python it just about works, but why would you do that when writing new code in 2020? Python 2 is officially dead and upgrades between the 3 sub-versions are basically painless. Very little justification for sticking to pre-3.5 versions of python anymore.

7

u/i9srpeg Jan 02 '20

I'm using type hints on a 100k LOC Python backend, and I'm also using Typescript on the similarly sized frontend. The difference is night and day. Mypy/pyright are slow (as in, several seconds between typing and seeing the errors show up). They're unreliable: they have both false positives and false negatives. They're buggy: they crash all the times. Python libraries either have no type hints at all, or they're sprinkled with Any. Type hints syntax is simply horrible and forward/circular references are a pain. Reusing expressions syntax for types and making the hints executable at run time were big mistakes. Type hints add a ton of verbose boilerplate and in the end they fail at the most important thing: ensuring type safety. Even a simple class rename, which is 100% reliable in all static languages is not safe at all in Python. You always need to run unit tests and manually check the code to make sure everything is renamed correctly.

It was nice to start with project with Python and it worked great at first. Now, after 3 years, I'm wishing I picked a statically typed language.

1

u/ZombieRandySavage Jan 02 '20

As long as I consistently use a language function that isn’t enforced (and was only recently introduced) across an entire team of developers— it’s fine!

Sounds good lol.

Type hinting is a bandaid on a gunshot wound. It helps, but it doesn’t solve the problem and it forces you to make design choices that are opposed to the whole point of using a dynamic language.

9

u/[deleted] Jan 02 '20

Yup same, or at least for the stuff our team works on. Basically anything that’s not meant to be a daemon or ran on many hosts / performant is python, everything else is go.

Mostly for the simplicity of deployment. There’s very few things that are “performant”, but some of the concurrency patterns in go are also just a lot more intuitive. Imo it’s really hard to beat channels and goroitines.

1

u/garlic_naan Jan 02 '20

I am not a developer but use Python in analytics. How easy / difficult it is to write different parts of same application in different languages? Does it not create compatibility issues?

1

u/ketralnis Jan 02 '20 edited Jan 02 '20

It varies a lot. There are in-python tools like numpy and Cython, then there is the C extension system which can go pretty far (which we use to call into both C and rust). If you’re built in a services style then whatever RPC system you use is probably language agnostic. Those are the easy ways but if those aren’t available it’s still possible but awkward to cross language boundaries

-10

u/Leon_Vance Jan 02 '20

Yeah, you will be productive now, but will you be productive in the same project in a year?

-18

u/SedditorX Jan 02 '20

It's unlikely that your work place is having the same challenges as a larger company even though your using the same language.

19

u/ketralnis Jan 02 '20

I work at reddit

16

u/Amablue Jan 02 '20

Never heard of 'em.

1

u/[deleted] Jan 02 '20

Most likely you aren't working on the scale that dropbox is though.

... most likely

243

u/Agent_03 Jan 02 '20 edited Jan 02 '20

A more detailed explanation:

  1. Avoid needless processing. This breaks down two ways

    1. Feature design: Think hard before adding features that come with significant performance impacts -- do you really need this feature? Is there a simpler way to do it which achieves most of your goals? Can you do it a simple way 90% of the time and only fall back to something more complex if needed? Can you skip several intermediate steps to get to the end result faster? (ex avoiding sorting a list)

    2. Optimize execution by taking advantage of short-circuit evaluation and doing lazy fetching/evaluation. For conditionals, if you sometimes need to do an expensive check, but usually don't, then see if there's a way you can skip that check. Laziness: don't fetch extra things from the filesystem until requested, if you often don't need it.

      1. Practical example: I optimized a routine (in Python) at work last month. We were processing text files a line at a time and removing control characters. To remove control characters we used a regex on each line (not the most efficient approach, fairly expensive). I added a quick check that iterated through the line of text and checked if any of the characters were within the control character range,and just returned the original string if not. Not as efficient as rolling a non-regex implementation, but since control characters are rare it avoids 90% of the performance cost and was much simpler & safer to implement.

  2. Cache results of expensive operations to avoid repeating them unnecessarily. If you're fetching info from the filesystem, cache it in memory if you are likely to reuse it (works well with lazy evaluation).

  3. Batch it: if you're doing a single operation often to many items, try gathering up the items to process and processing them in large groups. Often this is more efficient because it makes better use of caches (CPU/disk) and it permits you to write much tighter loops for processing. It permits reusing buffers, connections, SQL prepared statements, etc. It can improve branch prediction, permit use of SIMD instructions, etc where they would not work otherwise.

    1. Batching also makes it easier to fall back to something like the multiprocessing library to parallelize work.

  4. Use software pipelining. This is kind of like batching: rewrite loops that run items through a series of steps/processes so you first do the same step to each item, then the next step. Sometimes can be evaluated much more efficiently by compilers/interpreters because it allows using SIMD instructions, avoids branch prediction misses, etc.

    1. May also mean using Unix/Linux pipelining as well: use a bunch of smaller utilities that pipe input from one to another. This is another application of the same principle, but has the extra advantage of being generally very efficient, and spreading work across multiple processors.

  5. Use a lower-level language than Python to optimize the most performance-sensitive parts of the code. I.E. fall back to C bindings for intensive number crunching, crypto, etc. Optimized C can be several times faster than Python (or sometimes much more!). In general Pareto's principle applies: 80% of your execution time comes from 20% of the code (and vice versa), so if you double the performance of the slowest 20% you can almost double your overall performance.

69

u/EternityForest Jan 02 '20

"Do it a simple way 90% of the time and only fall back to something more complex of needed"

Now that's the right way to do simple software!

Don't just remove the feature, dynamically enable it as needed.

12

u/Agent_03 Jan 02 '20

To explain a bit further:

This is for cases where it's far more complex to replace with an optimized implementation or better algorithm that covers all the edge cases, or where there is an implementation with lower big-O complexity but a much higher constant overhead.

For example when writing a sorting algorithm you check if numbers are already sorted before trying to sort them, right? And in many languages the default implementations for sorting numbers usually use a quicksort for the bulk of it, but often switch to an insertion sort when the number of elements is small (7-10 or so). Insertion sort has worse big-O scaling but is faster for small numbers of elements.

In general, often you can write a quick and dirty brute force solution to a problem that covers all the edge cases but has poor big-O performance (for example, depth-first search of a graph). There are much, much more efficient algorithms you can apply but they usually require some assumptions about the structure of the data -- and if you know that your data violates one of these, you simply can't use them. The more optimal algorithms often require more complex data structures as well, which makes them much slower for small n values.

As an example of this, radix/bucket sort is hands-down the fastest option for large sets of smallish or fixed-length elements (say, 2-4 byte integers). But you have to be able to be able to split inputs into multiple buckets -- if you can only do comparisons for some elements then you have to be able to fall back to quicksort/mergesort etc.

Finally, if performance is bad enough that you're addressing it then simplicity takes a second priority to speed.

2

u/ManvilleJ Jan 02 '20

Finally, if performance is bad enough that you're addressing it then simplicity takes a second priority to speed.

to state this another way, Simplicity takes a back seat ONLY when performance becomes a bad enough problem.

3

u/Agent_03 Jan 02 '20

Correctness > Simplicity > Performance.

Except that in some applications a certain level of performance is part of correctness. Failing to plan for that constitutes a bug.

Simple code is often performant code as well.

1

u/EternityForest Jan 16 '20

I'd say performance is far above simplicity for a lot of applications.

If someone gave me a choice bet two similar programs, one that was 100 lines and takes five minutes, and another one that's 1000 lines but takes half that, I'm going to choose the 1000 line one every time, so long as they convince me they have correctness down.

Complexity needs justification, but it doesn't make a product crap(Unless you're main goal is to reduce attack surface for security).

Whether or not you can get correctness in a complex product with your team, tools, and deadline, for your particular application domain, is another matter.

A lot of the highest performing stuff is because of JITs, compression, prediction, etc. Simple stuff is often performant because the user does a lot of what the complex software would be doing.

17

u/Astrokiwi Jan 02 '20

For (5), this is why we use libraries like numpy, or compiled thingees like Cython.

14

u/Agent_03 Jan 02 '20

Yep, and libraries like PyTorch or PyCuda that can leverage GPU acceleration via native bindings

6

u/geeshta Jan 02 '20

Nice reply, thank you! I want to ask how would you do crypto in C? The problem I'm having is that with Python you have (almost) infinite integers and in cryptogryphy, numbers of tens to hundreds of digits (in base 10) are used. I alway wanted to rewrite my factorization/encryption/decryption libraries that I wrote in Python to C to see the performance increase but always struggled with C's MAX values for integers.

10

u/Hydroel Jan 02 '20

Are you using C's long, long long integers, or even double precision floating point numbers? I don't know the range of the variables you're using in cryptography, and you might be using numbers over 2^18; but I'm pretty sure Python relies on the same number implementation as C, so I'd be quite surprised if it could do anything that C cannot do (albeit with a simpler syntax)

17

u/geeshta Jan 02 '20 edited Jan 02 '20

The python integers don't use any C primitive type, they are objects with dynamically alocated memory, that's why they can be almost infinite, as long as you have memory available. Also that's why they are so slow. Anyway the implementation in C is beyond my understanding.

The thing is that in cryptography you would nowadays use 1024 or 2048 bit keys for encryption (RSA-1024, DH 2048) and it will probably even grow in the future. We're talking numbers 10^200 and more. In Python this is no problem but with languages with a fixed number bit-size, it is.

But maybe there are some libraries or ways to store those numbers in arrays or something.

7

u/Hydroel Jan 02 '20

That makes sense, and I didn't know that about Python! I just tried inputting using a sha1 in Python (which is unique and therefore the largest complex integer I could think of, as a matter of fact in the 2159), and it is indeed completely straightforward. Thank you for your short explanation.

After looking around (very shortly, I must say), you're not the only one with that issue, and GMP seems to be the preferred choice for cryptography in C.

cryptography you would nowadays use 1024 or 2056 bit keys

That would be 2048, not 2056, wouldn't it?

1

u/geeshta Jan 02 '20

Oh yes, fixed, I mixed it with 256. And thank you for your advice, the library looks promising, I haven't actually done any research on that yet.

4

u/AntMan5421 Jan 02 '20

Hey, I'm not OP nor experienced programmer in C.

You might want look into bitsets and arrays of integers.

Here are some potentially helpful links:

https://stackoverflow.com/questions/2252896/how-do-you-store-an-arbitrarily-large-integer-value-in-memory

https://stackoverflow.com/questions/4372515/how-to-implement-a-bitset-in-c

3

u/TheBlackCat13 Jan 02 '20

CPython uses C 32-bit integers behind-the-scenes if the value is between -230 and 230. It only falls back to dynamically allocated sizes if the number exceeds that size. You can see more details here. The C API has access to the underlying C integer if it is available and can use fast code paths to optimize calculations using them.

1

u/fireflash38 Jan 02 '20

The thing is that in cryptography you would nowadays use 1024 or 2048 bit keys for encryption (RSA-1024, DH 2048) and it will probably even grow in the future. We're talking numbers 10200 and more. In Python this is no problem but with languages with a fixed number bit-size, it is.

Ehhh, not likely to grow in the future. 2 or 4k is large enough, and 8k is overkill. And if you can break 4k, you can break 8k.

Most things should be doing ECDHE anyways for forward secrecy. Once you get into quantum though, that's a whole different set of problems.

0

u/DiggV4Sucks Jan 02 '20

In Python this is no problem but with languages with a fixed number bit-size, it is.

It's not a problem? Why would it be a problem? Do you think that Python is implemented on machines with unlimited bit-sizes? Couldn't you duplicate the Python's integer implementation in any language?

I mean really... Do you think that there is no crypto implementation in C?

2

u/TheBlackCat13 Jan 02 '20

Never used floating point numbers when you need the number to be exactly correct. A lot of weird things can happen with them in often unexpected ways.

5

u/AngriestSCV Jan 02 '20

You are looking for what is known for as an arbitrary precision library.

Here is an example https://gmplib.org/

The macros MAX_INT, MAX_LONG ... etc will let you know at compile time how big your integers are. There is also uin32_t and it's friends that let you specify exactly what kind of integer you want.

1

u/geeshta Jan 02 '20

Yes that's exactly what I was looking for. Thank you.

3

u/fireflash38 Jan 02 '20

Check openssl's 'bn' methods

And unless you're doing it for educational reasons, I wouldn't roll your own crypto, there's a billion pitfalls.

1

u/geeshta Jan 03 '20

Thank you that looks very useful. I'm not rolling it anywhere, i really is for educational reasons.

1

u/ak217 Jan 02 '20

The first rule of crypto is to not do your own crypto (unless you're just trying to learn).

Use libraries rolled by the pros. https://github.com/pyca/cryptography and https://github.com/wbond/oscrypto are a good start. Even they get plenty of things wrong, but when they do, they will alert you. If you can't commit the level of support those authors do, then you can't afford to roll your own crypto.

4

u/Isvara Jan 02 '20
  1. If you're fetching info from the filesystem, cache it in memory if you are likely to reuse it

Why isn't it better to leave this to the operating system, which has better whole-system view?

4

u/Agent_03 Jan 02 '20

Often it is, if you just want the raw bytes. If you're doing some sort of analysis on the data it's more efficient to cache the result yourself though, or if your program knows more about the access pattern.

4

u/Fourgot Anaconda3 science-like Jan 02 '20

Why isn't it better to leave this to the operating system, which has better whole-system view?

It can be, if the particular constraint is memory. If the bottleneck is actually IO, then leaving the data in memory prevents repetitive expensive reads.

1

u/AngriestSCV Jan 02 '20

The os dosn't know your application. For instance if you do an expensive db query that can be slightly out of date and still useful you might want to return that value multiple times. The OS can't know what you are asking of the db. The db might be able to be configured to cache the result as you need it, but that isn't automatic.

4

u/[deleted] Jan 02 '20

Thanks for your post. As a hobbist, learning things that are probably common knowledge to you is extremely useful!

2

u/atomicspace Jan 02 '20

nice comment.

2

u/Zegrento7 Jan 03 '20

For (4), here's an example: Let's say there's 1001 items that need to be processed with an 8-step task. Each step takes one second to complete.

Without pipelining, an item needs to pass through all steps before the next item can be processed, so the last item needs to wait 8000 seconds before it can be processed.

With pipelining, once the first step finishes processing an item, it passes it to the next step then starts working of the next item while the next step is working on the previous item. This means that a new item enters the first step every second, so the last item only has to wait 1000 seconds before being processed. An 8x speedup.

1

u/Agent_03 Jan 03 '20

That's a much better explanation than the one I gave

1

u/abeardednerd Jan 02 '20

is it okay that i don't understand any of this ? or am i just dumb !

4

u/Agent_03 Jan 02 '20

No, you're not dumb -- a lot of these things you only need to worry about when running performance sensitive code or production code at a fairly large scale.

For 90% of things, performance isn't a critical consideration as long as you use standard libraries.

2

u/abeardednerd Jan 02 '20

well, that's reassuring !

2

u/sibswagl Jan 05 '20

I'll try to define as many of the more complex terms as possible. And like Agent_03 said, this is fairly complex stuff. There's a scareword in programming called "premature optimization" -- basically, write simple and correct code first. Then, if the speed is actually negatively affecting the product, add complicated stuff like caching and batching. A lot of the time you won't need to.

  • short-circuit evaluation: Boolean operators (eg. && and ||) perform what's known as short-circuiting, wherein they only evaluate as much of an expression as necessary. For example, if you have A && B and A evaluates to false, then you can skip checking B (because regardless of its value, false && B is false). Therefore, you can structure your expressions so the more expensive values are evaluated last. If A takes 50 seconds to compute and B takes only 5, you should do B && A.

  • lazy fetching/evaluation: Pretty much what it says on the tin. A lot of times programmers will over allocate or over fetch to be on the safe side, eg. creating an array of 10000 objects and instatiating all of them. This is safer because if you access any index in the array, you know the object exists. However, it's also slower if, on average, you only access 100 of the objects. It's faster to instatiate each object the first time it is used, so you aren't doing uncessary work.

  • Caching: Fairly simple in concept (save the results of previous operations), but can be tricky in practice. There's a lot of stuff to read on caching, if you're interested.

  • In addition to manual caches (ie. you create and maintain it), there are also system level caches for retrieved memory. Because memory is retrieved in chunks (which are then stored in the cache), if you can ensure as much of your data is on the same chunk as possible (instead of spread across multiple), this helps speed up your code. A cache miss is when something is no longer in the cache, so the computer has to retrieve the memory again (much slower); keeping your data close together helps avoid this.

  • Branch prediction: Compilers and processors like to try and guess what your program is going to do. If you have a condition inside a loop that evaluates to false 90% of the time, this time it is probably also going to be false. Therefore, the computer can "skip" some work to help speed things up. Similarly to cache misses, branch prediction misses are when the compiler/processor guesses wrong and has to slow down to do some makeup work.

  • SIMD instructions: (I think) these are a type of machine level instruction that use parallelism to speed up work

1

u/scatters Jan 02 '20

For 1.2.1, were you really iterating through the line character by character? I'd have thought that using a precompiled regex search for control characters would be fastest since that can be heavily optimized.

2

u/Agent_03 Jan 02 '20 edited Jan 03 '20

Yes, really. Regexes use state machines internally and can have some surprising complexity and performance characteristics. Stack overflow had an outage due to one regex issue.

For very simple operations (such as this one, where I just had to look at character codepoints and see if they fall in a couple ranges) the performance improvement from this change alone was substantial: for one dataset of several GB it cut a 15 minute process to about 13 minutes (there was a lot of other processing happening, so that was excellent for a single change).

Given we process a lot more data than the sample set, I expect considerable cost and time savings overall.

In general, regexes are great for more complex patterns but direct string operations are much faster for trivial cases. Unless you're processing multiple GB of text (I was) the difference probably won't matter to you, though.

Also when it comes to performance, always always always use a profiler to figure out which part is slow -- that's how I found this optimization.

Edit: Typos -- this is why you don't reddit on mobile, sigh.

0

u/[deleted] Jan 02 '20

go gang

85

u/[deleted] Jan 02 '20

Can someone please explain?

224

u/SwampFalc Jan 02 '20 edited Jan 02 '20

The way I read it (which might be wrong) is that, if you have a performance issue, you should try the following fixes in order (ie. try one and if that doesn't solve it, go to the next possible fix):

  1. Just don't do whatever you're trying to do. IOW ask yourself if it's really necessary/useful/something you might lose a client over.

  2. Cache the results of previous calls. Maybe you can reuse them as-is, or partially.

  3. Do a large number of calls in batch, maybe in advance or later, outside of peak operating hours. Or perhaps you need to set up a network connection to do what you're doing, if that takes a while then don't make a new connection for each request, bundle up a dozen and setup once.

  4. Don't add your stuff to an existing program, create a new and separate one that will take the output of a previous process. Decoupling, in a way.

  5. If none of that works, only then should you look for a totally different way of doing it.

69

u/Agent_03 Jan 02 '20

There's multiple explanations for these, which makes them deeper than they seem, but there's a couple more parts:

  1. Not doing work may include several ways of avoiding extra computation -- lazily running expensive operations if not always needed, adding conditional checks before complex work rather than throwing exceptions, using short-circuit evaluation, or using more efficient algorithms / cutting out intermediate steps if you can get a result without them.

  2. Yep.

  3. Yep, but it doesn't necessarily have to wait hours -- batches of work can be handed off to other processes or utilities to process (makes better use of cores), and often you can write tighter loops that make better use of caches and reuse resources (connections, buffers, etc)

  4. That's Unix pipelining, and it's good shit, but software pipelining is a more general version of the technique. Depending on your architecture one or the other may be more efficient -- goes well with batching above though.

  5. No, this is a reference to falling back on C bindings invoked from Python, and writing the really tricky bits highly optimized in a lower-level language. C can be several times as fast as Python (or more, with good use of SIMD instructions) if written efficiently.

    • They didn't do this often at Dropbox, because Python is faster to write and easier to maintain, but when they did this they got huge speedups.

Hope this helps -- I swear I saw a talk the Dropbox folks gave on Python performance some years ago.

22

u/WikiTextBot Jan 02 '20

Software pipelining

In computer science, software pipelining is a technique used to optimize loops, in a manner that parallels hardware pipelining. Software pipelining is a type of out-of-order execution, except that the reordering is done by a compiler (or in the case of hand written assembly code, by the programmer) instead of the processor. Some computer architectures have explicit support for software pipelining, notably Intel's IA-64 architecture.

It is important to distinguish software pipelining, which is a target code technique for overlapping loop iterations, from modulo scheduling, the currently most effective known compiler technique for generating software pipelined loops.


[ ^PM | Exclude ^me | Exclude from ^subreddit | FAQ / ^Information | ^Source ] Downvote to remove | v0.28

3

u/SwampFalc Jan 02 '20

I think that all 5 of these are very pithy descriptions of a wide range of techniques. For Dropbox specifially, #5 probably does mean going to C, but in any other environment this could easily mean using the GPU instead of the CPU, or maybe even to some other dedicated hardware. Which is why I tried to remain deliberately vague.

26

u/munificent Jan 02 '20

IOW ask yourself if it's really necessary/useful/something you might lose a client over.

No, it's at a lower level than that. It means don't spend CPU cycles doing unnecessary work. For example, say you need to find the greatest element in a list. You could sort the whole list and then pull the last element out. But sorting the entire list is more work than you need to do (it's O(n log n)). Simply find the max element and stop.

19

u/davvblack Jan 02 '20

Both interpretations are correct.

0

u/[deleted] Jan 02 '20

[deleted]

1

u/davvblack Jan 02 '20

But from a product design perspective (eg "something you might lose a client over") it's always worth asking if it's even worth building a given feature. It always adds complexity and maintenance cost to your project, and doesn't always add value.

1

u/mipadi Jan 02 '20

Don't add your stuff to an existing program, create a new and separate one that will take the output of a previous process. Decoupling, in a way.

I believe they are using "pipeline" in the CPU sense; i.e., if you have a multi-stage process that uses separate resources, overlap stages from multiple runs of the pipeline to increase throughput.

16

u/thescottjr Jan 02 '20

Im glad i'm not the only one who doesn't get it

51

u/feelings_arent_facts Jan 02 '20

If you need to optimize something for performance, the best thing to do is not do it at all. Basically rearchitecture it so that you don't need that logic anymore.

Python is notoriously slow so if you're going for performance, use C++ or C.

3

u/[deleted] Jan 02 '20

Thanks

3

u/[deleted] Jan 02 '20

How about 2,3,4?

26

u/Poromenos Jan 02 '20

Caching is doing it once and storing the result so it's faster in subsequent steps. Batching means doing many together instead of one at a time. Pipelining means splitting it up into steps so some of those can run in parallel instead of only starting one after the previous one is complete.

1

u/ericonr Jan 02 '20

Or Rust, or Go, or Java if you can wait for the start-up time, or D (which I believe Dropbox does use). Lots of options :)

25

u/sgenius Jan 02 '20

I'm pretty sure Dropbox uses D.

They would be Ropbox otherwise.

3

u/feelings_arent_facts Jan 02 '20

I need something more meme worthy. How about Nim? I hear that's new

2

u/ericonr Jan 02 '20

Just go for brainfuck then :)

2

u/andrew-dewitt Jan 02 '20

Dropbox actually uses a decent amount of Rust too

1

u/i9srpeg Jan 02 '20

Java if you can wait for the start-up time

JVM startup times should be around 90ms, which is usually OK unless you start and tear down the JVM for each operation.

1

u/ericonr Jan 02 '20

Is it that short? Java applications usually take much longer to launch for me than usual Python stuff.

3

u/i9srpeg Jan 02 '20

This article has some benchmarks: http://macias.info/entry/201912201300_graal_aot.md

I was surprised too when I saw JVM startup times so low. Most of the perceived slowness probably comes from the heavy, over-engineered frameworks which are commonly used in the Java world.

Quarkus seems like an interesting project. It starts up a REST API server in under 1 second when running on the JVM, and it fully supports GraalVM, which lets you generate a native binary that can boot in 0.016s. This is faster than Django startup times in my current project, but I don't know how the Java numbers would change for an application more complex than an hello world.

4

u/[deleted] Jan 02 '20

If you're a performance engineer, there are a couple of steps to follow:

  1. Don't be a perf engineer. What are you even doing? This is an awful job.

  2. If you've made it this far, just make sure you cache everything to save loads on your server

  3. Also batch the flying fuck out of your requests to cut down on constant streams

  4. Pipelines!

  5. If you've come this far, you are truly desperate: make sure you don't use Python.

That's how I've always looked at it anyway. Source: I was a perf engineer for a summer and should have listened to rule 1.

1

u/Bluestrm Jan 02 '20

What didn't you like about performance engineering? I'm not a full time performance engineer, but performance optimization is definitely one of my favorite types of work.

1

u/Agent_03 Jan 02 '20

I added what I think is a fairly canonical explanation of these rules as a new top-level comment.

They're kind of vague, and there's a couple interpretations.

46

u/nfojones Jan 02 '20

Ouch this gives me flashbacks of 2018 when I spent a year of my career performance tuning and refactoring a multifaceted data streaming application written in Python 2 that was running on the same box as the resource hungry Apache Flume agents it was feeding.

I managed some refactor miracles that year but the data we were consuming gave no fucks and kept scaling its way back to a bottleneck.

Started as a single threaded app that shift to a multithreading app and evolved into a multiprocessing stack that utilized ZMQ to talk between processes (I don't even know why I did that anymore). I learned an epic butt ton about Python that year but I'd prefer never to chase that problem again.

And of course this was a Fortune 500 megacorp that chose to lay me off in early 2019 because I fell into some arbitrary "doesn't work near a core location" layoff net (due to having convinced my boss to move across the country and keep the job). My boss and colleagues were shocked. For me though it was almost perfect timing. I'd done FT remote for almost 2 years and even though I was starting to come into a local office just to be around people I was definitely just coasting and that office had zero relation to my work. The chunky severance they gave me and the 60 days to find a new job worked perfectly. Got something like a 33% raise out of the new gig and the severance check arrived just as I was buying my first house.

Good times... feel bad for whoever had to pick that project up. I knew it like the back of my hand. One of those rare projects you actually built from the ground up one design mistake after another. At least it was well linted and relatively clean/sexy code with decent doc strings. And FWIW, it had finally made it to Python 3 just as I was leaving, having originally been confined to the RHEL Python 2.6 variant in its earliest days.

Sorry for the blog post. Sometimes I just leave these missives on Reddit for myself like a poor man's journal.

TLDR: I fucking love Python. Please never make me do realtime mission critical streaming with it again.

13

u/[deleted] Jan 02 '20

These kinds of long comments are why I love reddit, don't apologize for giving us quality content.

0

u/[deleted] Jan 02 '20

[deleted]

1

u/nfojones Jan 02 '20

Hey thanks. Just remember, what doesn't kill us makes us stronger. The know-how I gained was definitely worth it.

Forgot to mention I profiled the heck out of every dang step in the pipeline eventually trying to see where things were slowing down and realized eventually when you have competing processes on a box, figuring out exactly where the bottlenecks are coming from is like pinning jelly to a wall. Ultimately it helped but it was never 100% indicative of the root causes for the slow downs just that "yes here it is expanding and contracting its performance". Presumably classic fallout from variable pipeline throughput causing resource exhaustion. Reading incoming data slows down as your output runs into bottlenecks and so on and so forth. Ripple effects. Go figure, many of the water analogies around streaming data really do make sense.

My internal name for this project was Tsunami Surfer. When it started it was a tongue-in-cheek name but by the end it seemed relatively apt.

Good luck with your project! May you one day leave it to some hapless new hire, as is tradition.

PS. I also eventually migrated some of the pipelines to run on PyPy. That was probably the biggest single performance boost I got but had issues applying it to all the possible pipelines the codebase supported because getting your whole module stack to work with PyPy and your env can be a battle of its own.

7

u/MarsupialMole Jan 02 '20

How would you go about pipelining something in python ordinarily? I know of lots of pipeline type frameworks but not sure what would be my go to for arbitrary performance improvements within an existing application.

6

u/KyleDrogo Jan 02 '20

Was this posted before or after Guido left?

2

u/nevus_bock Jan 02 '20

I remember you. You’re just a troll who shits on Python for some reason. Last time you were plugging Lua; still on it?

-2

u/stefantalpalaru Jan 02 '20

Last time you were plugging Lua

You don't remember me.

You’re just a troll who shits on Python for some reason.

I'm just an experienced programmer and the current Tauthon maintainer. Who the fuck are you, down there in the peanut gallery?

2

u/nevus_bock Jan 02 '20

Yeah, you haven’t changed. Still a condescending douche. Good luck with python 2, Mr. “experienced programmer”.

-2

u/stefantalpalaru Jan 02 '20

Still a condescending douche.

Show me your code, you silly muppet!

2

u/nevus_bock Jan 02 '20

Why, would that somehow reduce your douchiness?

2

u/[deleted] Jan 02 '20

Wow. He really does have a hate boner for python. Odd.

5

u/nuephelkystikon Jan 02 '20

I read it as ‘The rules of Perl’ first, which made the Python part a bit weird.

7

u/gitcraw Jan 02 '20

I was thinking "Performance Review" like corporate bullshit of bragging about yourself every 6 months to tell people whose job it is to keep track of you, what you're actually doing.

3

u/bradfordmaster Jan 02 '20

Same which is why I loved that step 1 was "don't do it"

0

u/[deleted] Jan 02 '20

[deleted]

8

u/synae Jan 02 '20

The only thing worse than working some place with performance reviews like that is working at a place without performance reviews.

Yes, they suck, but it's the easiest path to a raise/promotion if you don't want to job-hop every year.

3

u/axum2009 Jan 02 '20

Sounds like a Daft Punk song

2

u/poditoo Jan 02 '20

As a procrastinator I live my life by those very same words...

2

u/wildcarde815 Jan 02 '20

leaves out 'if you can make this work in osx and windows but not linux, that's fine abandon linux'.

3

u/lambdaq django n' shit Jan 02 '20

if you absolutely have to do it in Python, use some C module.

1

u/crazedizzled Jan 02 '20

Then you're kind of doing it in c.

1

u/FlukyS Jan 02 '20

Actually you can do it in python just make sure you break GIL. Worst case rewrite parts of it

1

u/AgentExodus Jan 02 '20

Do it in Python. Try it?

0

u/ManvilleJ Jan 02 '20

You know its funny, I hear it all over "python is has really bad performance". Then you hear the instagram story, then people talk about developer time cost, then people talk about the cost of computing and distributed computing. Somehow some java developer hops in to complain about white space and a lone cobalt developer start muttering about the good old days in his rocking chair.

The reality is, Each language is a good tool until it isn't. Usually, python is a good tool, but when it isn't, python is pretty good at bringing in the tool that is good at the job.