News for hackers. Stuff that matters.
Re:New Grad vs. Senior Dev by dimtion on Saturday March 28, 2020 @11:48AM (#22711810)
I find that the biggest misunderstanding happens because "new grads" (and I happen to be one) confuse _asymptotic complexity_ with actual complexity.

I'm not sure sure why, but CS courses and interview questions mostly focus on _asymptotic complexity_ and usually forget to take into consideration the complexity for "little values of n". And funnily enough, in real life n never goes to infinity!

In a strict sense big O notation only cares about what happens when n goes to infinity. The algorithm could behave in any way up to numbers unimaginable (like TREE(3)) but still, its big O wouldn't change.

Maybe what is missing to those "new grad" is a felling of real world data, and how a computer behave in the real world (with caches, latencies, optimised instructions etc...) not just having an ideal computer model in their mind when they design algorithms.

Re:New Grad vs. Senior Dev by corysama on Saturday March 28, 2020 @12:58PM (#22712394)
It’s because Big O is Computer Science. Cache effects are Software Engineering. Professors of CS do a fine job of teaching CS. They even briefly mention that there is a implicit constant factor k in O(k n log(n)) and then they never mention it again. They certainly don’t mention that k can easily vary by 128x between algos. AKA: 7 levels of a binary tree. Or that most of the data they will be dealing with in practice not only won’t be infinite, but will actually be less than 128 bytes. Or, that even with huge data and an proven-ideal O() algo, there is often 10x speed-up to be had with a hybrid algo like a b-tree instead of a binary tree. And, another 2-10x with SIMD vs scalar. 100x isn’t infinite, but it’s still counts.

So, grads listen to their CS professors and that’s what they know. It’s not until they get lectures from greybeard software engineers that they learn about the reality algos and not just the idealized algos.

Re:New Grad vs. Senior Dev by MaxBarraclough on Saturday March 28, 2020 @02:50PM (#22713386)
> briefly mention that there is a implicit constant factor k in O(k n log(n)) and then they never mention it again

A fine concrete example of this is the Coppersmith–Winograd algorithm (and its derivatives), a matrix multiplication algorithm with impressive complexity properties, but which in practice always loses to the Strassen algorithm, despite Strassen's inferior complexity. [0][1][2]

(Aside: the Strassen algorithm is pretty mind-bending, but also easily shown. If you've got 22 minutes spare, there's a good explanation of it on YouTube. Perhaps there's a more dense source elsewhere. [3])

> It’s not until they get lectures from greybeard software engineers that they learn about the reality algos and not just the idealized algos.

To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc.

[0] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...

[1] https://en.wikipedia.org/wiki/Strassen_algorithm

[2] https://en.wikipedia.org/wiki/Computational_complexity_of_ma...

[3] https://www.youtube.com/watch?v=ORrM-aSNZUs

Re:New Grad vs. Senior Dev by dwohnitmok on Saturday March 28, 2020 @03:54PM (#22713860)
Even Strassen can be overly expensive for reasonably sized matrices. Almost all matrix multiplication algorithms have a threshold only beyond which do they use Strassen.

Although apparently that threshold can be lowered (http://jianyuhuang.com/papers/sc16.pdf), but even then it's a matrix that's several hundred columns by several hundred rows large.

Some CS classes explicitly use Strassen to teach the realities of asymptotic vs wall-clock time complexity, challenging students to come up with a hybrid matrix multiplication algorithm that performs the fastest and switches at the best thresholds of matrix size.

Re:New Grad vs. Senior Dev by msla on Saturday March 28, 2020 @04:45PM (#22714188)
> To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc.

Which would have the positive knock-on effect of the textbook being sufficiently obsolete every year or so that the students could no longer trade it in for credit, saving the bookstores money!

More seriously, that knowledge (at least once you attach numbers to it) has a shelf life, and not a very long one. Teaching big-O analysis means the knowledge is timeless, which any good theoretical knowledge is, and moving more towards practice would force the professors to keep on top of the state of the art, and the state of the mainstream, of hardware design in addition to everything else they're doing.

Re:New Grad vs. Senior Dev by temac on Saturday March 28, 2020 @09:22PM (#22715597)
> Which would have the positive knock-on effect of the textbook being sufficiently obsolete every year or so that the students could no longer trade it in for credit, saving the bookstores money!

That's naive. E.g. SIMD is here since a good time and going to stay. So are GPGPU, with now quite similar architectures for tons of chips.

And Computer Science can actually be about science for real computers, and computers are not 8086 nor PDP11 anymore, and have never been a turing machine. So there actually is some existing generic CS and ongoing research that cares about cache effects and so over. Maybe it is applied CS if you want, and some kind of pure CS should not care about that, but I really don't see what should be the criteria to decide which is what anyway, so IMO there should not be any (but I do not mean that all research should care about e.g. cache effects, just that it is not really useful to attempt to distinguish between those which do and those which don't).

We don't teach advanced math by only showing what was done at e.g. the beginning of algebra. Neither should we stick to only basic subjects in computer science.

Re:New Grad vs. Senior Dev by MaxBarraclough on Saturday March 28, 2020 @08:11PM (#22715290)
> textbook being sufficiently obsolete every year or so

I wasn't very clear on that point, but didn't mean to suggest it be the same textbook. These other topics deserve courses and books of their own. The algorithms lecturer should be careful to emphasise the limitations of complexity theory though.

> that knowledge (at least once you attach numbers to it) has a shelf life, and not a very long one

Plenty of long-lived principles to be learned there, even if the particulars change over time. Caches are still going to be around in 10 years time.

Re:New Grad vs. Senior Dev by Tomis02 on Saturday March 28, 2020 @09:25PM (#22715611)
Without knowledge of the hardware your software runs on you're likely to be one of those people who uses lists instead of vectors without really understanding the difference. Also, as other people said, the shelf life for that knowledge is actually pretty long. Hardware will always be your platform, no matter how many layers of abstraction you have in between.
Re:New Grad vs. Senior Dev by LolWolf on Saturday March 28, 2020 @09:23PM (#22715599)
> To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc.

They are in many places I'm aware of. At least, as an EE (at Stanford, but I've heard MIT and several others do the same), I had to take a digital system design class, but the majority of the class was spent on performance engineering. In fact, the very first (actual) project of the class was to take a 10-line piece of C code, which applies a simple filter in real time to a video, and make it performant. The initial code runs at around .5 FPS.

Our resulting performant code was, of course, many times larger (I think it might have been ~150 lines), but it ran incredibly quickly (110 FPS, iirc), by doing crazy compiler tricks and often calling ASM from within the C code, even though the asymptotic (big O) performance was exactly the same.

For context, this is not just a digital systems thing (my work is in mathematical optimization theory and my undergrad was in photonics and physics), but I do know that this class is not a requirement for CS since it's potentially too hardware oriented. The classes exist, but I'm not sure people are taking them.

Re:New Grad vs. Senior Dev by MaxBarraclough on Sunday March 29, 2020 @10:57AM (#22719503)
> They are in many places I'm aware of.

Yes, sure. I hadn't meant to imply otherwise. The pure-algorithms lecturer needn't cover these other topics in detail in their course, but should be careful to emphasise the uses and limitations of complexity theory.

> this class is not a requirement for CS since it's potentially too hardware oriented

I don't see the sense in this. Computer scientists publish work on applying GPU acceleration, as they should - that's not electronic engineering work they're doing. We could quibble about whether it's computer science of software engineering.

Re:New Grad vs. Senior Dev by LolWolf on Sunday March 29, 2020 @07:53PM (#22723858)
> I don't see the sense in this. [...] We could quibble about whether it's computer science of software engineering.

I agree, I'm not sure why this is the case either, just my idea as to why it may not be a requirement. (Some part of the class does involve writing a good chunk of a 5-stage RISC processor based on MIPS, but this was still relatively straightforward with just a basic understanding of digital logic.)

Re:New Grad vs. Senior Dev by herbstein on Saturday March 28, 2020 @05:11PM (#22714359)
I always loved my algorithms and datastructures professor talking about Brodal queues[0] - a datastructure named after him. They're super interesting from a theoretical point of view, but they're not useful for anything.

[0] https://en.wikipedia.org/wiki/Brodal_queue

Re:New Grad vs. Senior Dev by MaxBarraclough on Sunday March 29, 2020 @05:00PM (#22722673)
That's a great example. Hadn't heard of it before.
Re:New Grad vs. Senior Dev by dilyevsky on Saturday March 28, 2020 @01:03PM (#22712433)
Every good cs course has a section on cache aware algorithms. And i call bullshit that constant factor is not mentioned too
Re:New Grad vs. Senior Dev by corysama on Saturday March 28, 2020 @01:25PM (#22712629)
It wasn’t taught to me. And, in my previous job I interviewed many dozen fresh grads. One of my questions was “How much slower is it to sum integers in a trivial linked list vs. a trivial array?” 90% answered “Umm... I don’t know. 2x?” When asked why, they all said “1 op to sum the int +1 op to traverse the pointer.” It was amazingly consistent.
Re:New Grad vs. Senior Dev by onekorg on Saturday March 28, 2020 @02:25PM (#22713159)
The answer could be 2x. Let's say you're in a 64 bit platform. Your linked list nodes consist of a next pointer and a 64 bit integer.

If your linked list nodes are all allocated sequentially in memory then it'd only be 2x as slow as an array of 64 bit integers.

But maybe it's not fair to call sequentially allocated linked list a "trivial linked list".

Re:New Grad vs. Senior Dev by koala_man on Saturday March 28, 2020 @04:20PM (#22714037)
This kind of CS-based rationalization is arguably another aspect of what the article comments on. I wrote a benchmark and found the difference in this case to be 3x-3.5x.
Re:New Grad vs. Senior Dev by willberman on Saturday March 28, 2020 @01:40PM (#22712784)
I can see how this wouldn’t be covered in an undergrad cs education. I took only a single computer architecture class which was extremely limited in scope. The only reason I knew about vectorization during undergrad is because a friend mentioned it to me once.
Re:New Grad vs. Senior Dev by temac on Saturday March 28, 2020 @09:25PM (#22715612)
The basic speed up will not even be because of vectorisation. It will be because of caches.
Re:New Grad vs. Senior Dev by willberman on Sunday March 29, 2020 @10:42AM (#22719368)
Are you saying that the majority of the speed up is from caches and then there's a secondary, much smaller, speed up from the vectorization? Or are you saying all the speed up is from caches and I'm off base here with vectorization.
Re:New Grad vs. Senior Dev by joshlemer on Saturday March 28, 2020 @02:44PM (#22713339)
What would be the kind answer you're looking for?
Re:New Grad vs. Senior Dev by corysama on Saturday March 28, 2020 @03:12PM (#22713560)
The question had 2 goals:

1) Do you think about cache at all or is it just something you heard mentioned as important that one time?

2) It's a good lead-in to discussing the effects of cache in algorithms. How that conversation goes helps me to understand how that person thinks and discusses complex problems.

A good answer would be "I'm not sure, but probably way, way slower because linked list can point all over memory but arrays cache really well."

An excellent, A+ answer would be "In the best case it might not be too much slower if you have an intrusive linked list is arranged sequentially in memory like an array like onekorg explained. But, in practice most will be 20-200x slower because they are usually implemented as pointers to nodes containing pointers to data and each piece is allocated piecemeal in a already fragmented heap. Uncached memory reads can take 100+ cycles and summing an int is not enough work to hide that even if the CPU speculatively prefetches."

I mainly expect a surprised reaction that they could be so slow and looked forward to the follow-up discussion.

Re:New Grad vs. Senior Dev by TheOtherHobbes on Saturday March 28, 2020 @04:51PM (#22714236)
I sometimes wonder if CS should be renamed Computer Pseudo-Science. I blame Knuth and (mostly) Dijkstra for propagating the falsehood that you can estimate the performance of real code on real hardware with a some elegant academic blackboard math which gives you the wrong answer for many practical applications.

It's not that Big O isn't useful - it's that it's taught as a set of "proofs" which somehow make it appear objective and "correct", when in reality performance is at least as dependent on cache architecture, median size-of-n, memory bandwidth, and other implementation details.

Anyone who graduates CS without having been taught this very forcefully - preferably during a practical project - should be refunded at least some of their course fees.

Re:New Grad vs. Senior Dev by herbstein on Saturday March 28, 2020 @05:15PM (#22714389)
But Big O was a lot more directly correlated when the CPU wasn't doing "magic" optimizations on its own. It was still estimations with an invisible constant factor, of course,
Re:New Grad vs. Senior Dev by koreth1 on Sunday March 29, 2020 @02:32AM (#22716875)
This is a key point. The gargantuan performance difference between main memory and the CPU cache (or indeed, the existence of significant CPU caches at all) happened well after big-O was firmly established in the CS curriculum.
Re:New Grad vs. Senior Dev by Cpoll on Saturday March 28, 2020 @09:09PM (#22715550)
> But, in practice most will be 20-200x slower

My A+ answer is "My guess is [x] but instead of speculating we can create a test to discover the performance. [Describes test]."

Koala_man above says:

> I wrote a benchmark and found the difference in this case to be 3x-3.5x.

The actual number depends on a lot of things, of course (language, architecture, test methodology...), but it is possible that your 20-200x A+ answer is incorrect.

Re:New Grad vs. Senior Dev by temac on Saturday March 28, 2020 @09:29PM (#22715623)
There is no answers if you don't specify tons of parameters, like the number of element, prior memory fragmentation, etc.

200x can be a reasonable outcome. So can be 3x in other conditions.

As a rule of thumb I now consider that a completely random memory access is on the order of accessing 1000 sequential bytes.

Re:New Grad vs. Senior Dev by james_s_tayler on Saturday March 28, 2020 @09:20PM (#22715591)
Question... What kind of software do you mainly work on?

I'm guessing it's not CRUD apps.

Re:New Grad vs. Senior Dev by corysama on Sunday March 29, 2020 @12:55AM (#22716535)
High end 3D mobile games. We regularly measured direct correlations between performance and revenue. Higher performance meant a larger install base of devices could run the app with better responsiveness and lower battery burn. Thus, higher retention and engagement. Thus higher monies.
Re:New Grad vs. Senior Dev by jodrellblank on Saturday March 28, 2020 @03:38PM (#22713756)
At a guess, some understanding of this article[1] - if a CPU instruction scaled up to human time takes 1 second then a Level 1 cache lookup takes 2 seconds and a main memory lookup takes 4 minutes.

Imagine for the array it's 1 CPU instruction to load a value, 1 to load the next value, 1 to add them, and one to store the result, that would be 4 instructions per sum; ideally the array would stream into the CPU after a single main memory lookup delay up-front, and then be 4 instructions per pair, summed as fast as the CPU can loop.

The linked list at worst needs an imaginary 1 CPU instruction to load a value, 1 to load the pointer value, 1 to reference the pointer, a delay of 2 seconds to get that value from L1 cache - missed, it's not in cache - 240 seconds stalled waiting for main memory, 1 to add, 1 to store the result. Worst case, >240x slower.

The linked list is not guaranteed to be in contiguous memory, but it might be, so the cache might have the right data in it. The linked list is 50% data, 50% metadata, so the cache is half wasted / can hold half as much data, and if the linked list is coming in from a big memory read quickly, half the bandwidth is carrying pointer addresses not data, so the throughput is halved for that, too, and the processor cycles were already able to happen much faster than the main memory bus max speed. If it's not contiguous memory, you don't know in advance where it is to request all the right memory areas at once - not until you read sequentially to the last item pointer and find there are no more.

Maybe if they are both small, both in contiguous memory and go into Level 1 cache after a single main memory delay, it could be only ~2x time, but the more data there is overall, the more chance the linked list will bust the cache or be discontinuous in memory. And on the plain array side, it might be possible to speed up with SIMD/SSE instructions to spend fewer cycles adding and storing per element, which the linked list approach might not be amenable to at all[2], then best case might be ~4x slower, worst case ~500x slower.

[1] https://www.prowesscorp.com/computer-latency-at-a-human-scal...

[2] https://stackoverflow.com/questions/10930595/sse-instruction...

Re:New Grad vs. Senior Dev by cjfd on Saturday March 28, 2020 @01:44PM (#22712809)
O dear.... Am I happy that I never studied computer 'science'..... On the other hand, there must be smart computer science students and/or smart places of education where actual learning about processor caches and the like takes place.....
Re:New Grad vs. Senior Dev by lghh on Saturday March 28, 2020 @02:08PM (#22713005)
I don't think anyone answering in this way would be "not smart" like you seem to imply.
Re:New Grad vs. Senior Dev by dwheeler on Saturday March 28, 2020 @01:13PM (#22712520)
Mentioned, yes, but often not learned. In many situations the only thing that matters is the constant factor. If the number of data items is relatively small, the difference between N log N and and N squared may be completely dominated by the constant factor. In addition, there is the challenge of maintaining the code later and making sure it's correct.
Re:New Grad vs. Senior Dev by vvanders on Saturday March 28, 2020 @01:18PM (#22712567)
Yup, so much truth here.

Take a look at Real-time Collision Detection[1]. I takes a great look at both algorithmic complexity and cache awareness. That's how it should be done.

[1] https://www.amazon.com/dp/1558607323

Re:New Grad vs. Senior Dev by eyegor on Saturday March 28, 2020 @06:04PM (#22714672)
I've looked before, but I've never seen a class dedicated to practical algorithm design. Being able to reason about cache layout, context switch costs, branch prediction behavior, simd refactoring, and basic compiler level optimizations will result in much more performant code. In the real world people often write complex algorithms which operate on structs/classes instead of primitives. This means there's a huge performance hit just from pointer traversal in a hot path, especially if someone naively does math across data inside heap objects. You can easily write a fancy dynamic algorithm approach which has theoretical O(k*n) performance which takes forever in the real world due to abstraction traversal. If you're doing more than one operation, it's often a massive performance boost to cache all your object pointer evaluations into primitive arrays, do simd operations on them, and then populate the objects at the end.

Does anyone have a good textbook suggestion for cache/simd aware algorithm design? I've seen plenty of papers that cover single examples but never something the scope of a book.

Re:New Grad vs. Senior Dev by willberman on Saturday March 28, 2020 @01:36PM (#22712740)
When I took data structures and algorithms, I believe almost every single lesson was concluded with the caveat that constants are important.
Re:New Grad vs. Senior Dev by lonelappde on Saturday March 28, 2020 @01:20PM (#22712586)
That's an arbitrarily restrictive view of computer science. It's like saying teaching physics ignoring friction perfectly fine.
Re:New Grad vs. Senior Dev by pretendscholar on Saturday March 28, 2020 @01:36PM (#22712744)
Yes you should ignore the details of friction for the first few semesters.
Re:New Grad vs. Senior Dev by lonelappde on Saturday March 28, 2020 @01:39PM (#22712774)
For how many semesters? All the way through to graduation?
Re:New Grad vs. Senior Dev by eternauta3k on Sunday March 29, 2020 @12:30PM (#22720259)
Funnily enough, you only solve problems with friction in your first semester (and maybe a little bit afterward when you study waves).
Re:New Grad vs. Senior Dev by rriepe on Saturday March 28, 2020 @01:43PM (#22712805)
No. You wouldn't want people slipping on stage.
Re:New Grad vs. Senior Dev by alasdair_ on Saturday March 28, 2020 @05:11PM (#22714358)
> No. You wouldn't want people slipping on stage.

Since all the students will merely be spheres of equal density, that shouldn’t matter much.

Re:New Grad vs. Senior Dev by bialpio on Sunday March 29, 2020 @03:03AM (#22716981)
I guess in that case you can also skip teaching them about angular momentum!
Re:New Grad vs. Senior Dev by saagarjha on Sunday March 29, 2020 @04:06AM (#22717226)
They’d still have angular momentum; it just wouldn’t be immediately apparent.
Re:New Grad vs. Senior Dev by Jasper_ on Saturday March 28, 2020 @02:34PM (#22713235)
Models are easy when you turn every cow into a sphere. But physicists never believe their models respect the real world. Computer Science should be about the Science of Computers, not hypothetical models acting on hypothetical architectures.
Re:New Grad vs. Senior Dev by duck2 on Saturday March 28, 2020 @02:46PM (#22713354)
Computer Science existed long before there were computers. I think the Science of Computers you mention is known as Computer Architecture.
Re:New Grad vs. Senior Dev by msla on Sunday March 29, 2020 @03:27AM (#22717075)
> Computer Science existed long before there were computers.

No, various bits and pieces of it did, but not the whole, coherent field, which is motivated by the existence of computers.

Re:New Grad vs. Senior Dev by msla on Saturday March 28, 2020 @04:46PM (#22714195)
> Computer Science existed long before there were computers.

Not in its current form, and not if you define "computers" with a sufficiently broad net.

(Or broad loom, tipping a hat to Jacquard... )

Re:New Grad vs. Senior Dev by jrs95 on Sunday March 29, 2020 @05:24AM (#22717513)
And then we seriously overvalue these "core CS skills" for a lot of positions, many of which will not involve actually using any of it at all. I can't tell you how many people I've worked with that could tell you a bunch of Big O crap off the top of their heads but all they were working on was web apps and they couldnt seem to remember that running an ORM query in a loop is a bad idea. The way the U.S. uses college education as a prerequisite to employment but also seems to not be very good at teaching stuff that's actually relevant to the work you allegedly need the degree for is very disturbing to me.
Re:New Grad vs. Senior Dev by fchu on Saturday March 28, 2020 @04:08PM (#22713947)
As a side note: O(k n log(n)) and O (n log (n)) have exactly the same meaning for k non-null constant by the definition of big O notation. The more you know!
Re:New Grad vs. Senior Dev by Zarel on Sunday March 29, 2020 @02:20AM (#22716835)
After a few years working on real-world code, I understood that faster asymptotic complexity was often slower on average.

After a few more years working on real-world code, I understood that it's usually better to choose the algorithm with better asymptotic complexity, anyway.

Like, sure, my O(n) algorithm will be 10x slower than your O(n^2) algorithm for small n. But users aren't going to notice a few microseconds. Users ARE going to notice my O(n) algorithm being 100000x faster for large n, when it's the difference between milliseconds and minutes.

Re:New Grad vs. Senior Dev by 3pt14159 on Sunday March 29, 2020 @06:37PM (#22723430)
It's a tough call sometimes. Code legibility is important and an O(n^2) is so often fast enough (microseconds!) that a more complex algorithm may be faster for the 0.001%ile and you're right that sometimes that means we should select it, because it makes the worst case still microseconds, but realistically speaking some codepaths change frequently enough that the true metric of a codebase is how easily it's adapted, understood, or modified. Let the guy with the big n eat cake, so to speak.
Re:New Grad vs. Senior Dev by justinmeiners on Saturday March 28, 2020 @12:18PM (#22712086)
I regularly see people make this mistake and don't grasp it after correction.

You could make a hash table with a constant time lookup, but the hash takes 1 hour. Big oh only tells you how it scales, not it's performance (runtime).

Re:New Grad vs. Senior Dev by TeMPOraL on Saturday March 28, 2020 @12:21PM (#22712110)
It's not even that. You could have a normal hash table with a decent hashing function, and you'll still get beaten by a flat array for small n (hundreds, low thousands), because the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache.
Re:New Grad vs. Senior Dev by dmoy on Saturday March 28, 2020 @12:27PM (#22712152)
> the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache

Also - if I see someone try to use a linked list for an enormous data structure again.... Wow it does not scale worth crap because it turns out that the hardware is actually important, and contiguous memory is amazing.

Re:New Grad vs. Senior Dev by TeMPOraL on Saturday March 28, 2020 @12:32PM (#22712194)
Oh god. Don't talk to me about linked lists. One of the bigger performance improvements I've made in a certain company is taking the code working with lots of numerical data in linked lists because they had easier syntax, and rewriting it using honest-to-god, contiguous-memory arrays of doubles. After that, we could process three orders of magnitude more numbers per operation, and one order of magnitude more of operations, and we still came ahead.
Re:New Grad vs. Senior Dev by matwood on Saturday March 28, 2020 @01:27PM (#22712648)
Maybe you knew the scale up front, but if you didn’t the easier syntax was the right first choice. It may have been the right first choice because it was easier to code even with the scale known up front. Only after measuring and understanding the trade offs should the easier to reason about code have been removed. IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer.
Re:New Grad vs. Senior Dev by TeMPOraL on Saturday March 28, 2020 @01:37PM (#22712758)
> IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer.

I agree, but in a way opposite to what you intended. An experienced developer[0] should be able to look at a situation like this and realize that few more minutes of focus can yield a better (array-based vs. list-based) implementation[1]. There are no downsides to that (arrays were only slightly less convenient in that case, syntax-wise), improvements occur regardless of scale. The list-based solution was a bad one at the scale it was originally written for handling.

I believe a hallmark of an experienced developer is writing performant code from the get-go; this is accomplished by not making stupid mistakes like this, and it costs pretty much nothing in terms of coding time or code complexity. All it takes is a little knowledge and caring about the product's performance.

--

[0] - I hesitate to use the word "senior", because to me, whether it means anything depends on the company one works in. In many, a "senior" developer is just the one that came before all the "junior" hires, and it doesn't matter that that developer is a fresh bootcamp graduate. And once you can put "senior X developer" on your CV, it's likely your next job will give you seniorship immediately as well.

[1] - and an extra few more minutes would give an implementation that doesn't allocate new memory unnecessarily - also a huge performance win.

Re:New Grad vs. Senior Dev by codr7 on Saturday March 28, 2020 @04:14PM (#22713997)
The most important lesson I've learned from 34 years of writing software, it's to stop pretending I know shit about the problem I'm trying to solve before I have written an actual working solution. Which means getting there asap is top priority and nothing else matters. Sometimes that code runs fast enough, often it turns out I'm solving the wrong problem which means performance doesn't matter at all.
Re:New Grad vs. Senior Dev by jayd16 on Saturday March 28, 2020 @02:33PM (#22713228)
In this case complexity analysis would tell you that.
Re:New Grad vs. Senior Dev by alexis_fr on Saturday March 28, 2020 @12:54PM (#22712358)
> if I see someone use a linked list

Or a hashmap to prepare 3 variables to pass to Json serialization.

Re:New Grad vs. Senior Dev by leetrout on Saturday March 28, 2020 @01:22PM (#22712601)
I think that hits the human factor of software development where it is easier to conceptualize your hashmap will become that JSON object.

Curious - what would be your solution? Just creating the json directly as strings / bytes?

Re:New Grad vs. Senior Dev by dasyatidprime on Saturday March 28, 2020 @02:11PM (#22713030)
Unsorted-array-based maps are sometimes used in the Java world, and for two or three elements will have much less overhead than hash tables. For instance, fastutil has http://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/objec.... The map interface and encapsulation into a single “object” is the same.

It occurs to me that I don't know whether any of the major dynamic language implementations with maps/dicts/hashes as a central data structure use a similar approach for very small ones… huh.

Re:New Grad vs. Senior Dev by deathanatos on Saturday March 28, 2020 @01:45PM (#22712828)
> by a flat array for small n (hundreds, low thousands)

Some of us are working in, say, Python. A flat array can outperform at small n, yes, but people overestimate where the tradeoff point is. It's at <5 items:

  # A list of [0, 1, 2, 3, 4]
  In [10]: linear = list(range(5))                                                                                                                    

  # A hash set, same thing.
  In [11]: hashing = set(range(5))                                                                                                                    

  # 44ns / linear search
  In [12]: %timeit 3 in linear                                                                                                                        
  44.2 ns ± 0.412 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

  # 25ns / hash search!
  In [13]: %timeit 3 in hashing                                                                                                                       
  25 ns ± 0.6 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
The hash set outperforms the linear search by nearly 2x, on a list of size 5! (The performance is similar for other common types that end up in hashes, like strings.)

"It's Python!", you say. "Too much chasing of pointers to PyObjects destroy the cache!" And yes, they do; but many people are working in high-level languages like Python or Ruby.

But, for those that aren't, if we repeat the above exercise in Rust, yes the tradeoff will move up, but only to ~60 items, not hundreds or low thousands:

  test tests::bench_hash_int       ... bench:          14 ns/iter (+/- 1)
  test tests::bench_linear_int     ... bench:          19 ns/iter (+/- 3)
If you're thinking that somehow accessing the middle item each time bestows an unfair advantage to the hash table, randomizing the desired item doesn't help, either:

  test tests::bench_rng_hash_int   ... bench:          19 ns/iter (+/- 2)
  test tests::bench_rng_linear_int ... bench:          24 ns/iter (+/- 2)
And looking for an item not in the list is definitely not favorable to the linear search. (It's the worst case.)

In my experience, it's almost always easiest to pay mild attention to big O concerns, and just use the appropriate data structure for the problem at hand. Cache effects mattering is either rare (you're writing a RESTful microserving to push cat pictures, a cache isn't going to matter once we hit this mobile devices 20 second network latency!) or highly context dependent (your line of work is always low-level, and these crop up more often, and you're consequently on the lookout for it; I don't think this applies to most of us, however).

The code used, in case you wish to find fault with it: https://github.com/thanatos/hash-vs-linear

Re:New Grad vs. Senior Dev by XelNika on Saturday March 28, 2020 @04:09PM (#22713960)
You only benchmarked the search itself, but in the real world it might also take time to set up the data. You can't really pinpoint a tradeoff point without knowing how many times a data structure will be used.

I ran your Python test on my machine and the hash set was faster in every case: 10x faster at size 50, 2x faster at size 5, 1.3x faster at size 3.

Re:New Grad vs. Senior Dev by deathanatos on Saturday March 28, 2020 @08:15PM (#22715310)
That's not a bad point, and perhaps I should test creation times too. (I wanted to ignore that s.t. the test isolated a single thing: searching / wasn't mixing two things together.) Both hashsets and vectors are O(n) in setup, and I'd mostly expect their real-world performance to be very similar: hash tables tend to use contiguous arrays for storage and vectors do by definition, both tend to overallocate (hash tables to prevent collisions, vectors to amortize appends to O(1)), so I'd expect the performance in the real-world to be similar. Vectors tend to insert in-order, though, whereas the insertions in hashsets would bounce around the table, so that might make it more interesting.
Re:New Grad vs. Senior Dev by XelNika on Saturday March 28, 2020 @08:33PM (#22715401)
Yes, it's always best to reduce the number of variables in benchmarking, but the setup makes a big difference when we are talking about tiny data sets.

I don't know how to test it properly, but I tried looping over both the initialisation and a single search, and the hash sets were much slower, so much so that hash sets trailed lists by microseconds at size 10000. In retrospect, making those data structures unsurprisingly dominated running time and the test kind of lost all meaning. It was clear, however, that it wouldn't take many searches for the hash sets to win, search times for lists were going through the roof.

Re:New Grad vs. Senior Dev by justinmeiners on Saturday March 28, 2020 @01:49PM (#22712857)
I was using an extreme example to illustrate. I definitely agree.
Re:New Grad vs. Senior Dev by vvanders on Saturday March 28, 2020 @12:21PM (#22712107)
Yup, linear data reads are easily 10-30x faster than random thanks to cache miss penalty staying static since the 90s.

If you want to see real-world DDR speeds figure out what algorithms do linear reads.

Re:New Grad vs. Senior Dev by kevinventullo on Saturday March 28, 2020 @12:04PM (#22711938)
To be fair, in my experience it is often the case that asymptotic complexity is a good proxy for real-world performance, even for small values of n. Not always, but often.

I think it's fine that the academic courses focus a bit more on what's better in theory than in practice, because there are always caveats to "in practice"; the person who writes the special-purpose genomics libraries was also once a new grad.

Re:New Grad vs. Senior Dev by RookyNumbas on Saturday March 28, 2020 @01:03PM (#22712436)
I like to start by thinking about cache locality and ensuring linear layout. Next focus on one-time, or minimal memory allocation. Then there are a bunch of small, systemic things you need to get right. After that you can start worrying about worst case big O scenarios.

Of course this depends on your language. A c programmer will have a different mental model than a python one.

Re:New Grad vs. Senior Dev by lonelappde on Saturday March 28, 2020 @01:23PM (#22712603)
In Python performance is your last consideration, and that's OK. Most things computers do don't need to be fast. Only the innermost loops run the most do.
Re:New Grad vs. Senior Dev by SaxonRobber on Saturday March 28, 2020 @04:32PM (#22714112)
This is the philosophy that has led to our software becoming slower despite improvements in hardware.

Performance is always important. Especially for consumer applications, where your software will probably need to run alongside many other processes each competing for resources.

Re:New Grad vs. Senior Dev by celeritascelery on Sunday March 29, 2020 @08:19AM (#22718357)
> This is the philosophy that has led to our software becoming slower despite improvements in hardware.

I disagree. Software has gotten slower over time because we are adding more fluff to it (SDK’s, libraries, electron, GUI animations, web interactions, frameworks, etc). Not because the developers are failing to focus on code optimizations.

Re:New Grad vs. Senior Dev by why_only_15 on Saturday March 28, 2020 @02:35PM (#22713251)
i used to think this was true, but theres a lot of stuff recently where there really aren't such hotspots everywhere. when i profile UI stuff for instance there isn't some big obvious hotspot to optimize, the runtime is spread all throughout the app doing random things. if all the regular code you write is just ludicrously slow, you're going to end up with something that's just laggy and without any way to fix it other than rewriting it
Re:New Grad vs. Senior Dev by saagarjha on Saturday March 28, 2020 @12:15PM (#22712053)
Often, for small values of n performance matters less anyways matching that as n gets larger is often a nice bonus. Sometimes this makes the code more complicated, yes, but occasionally it can even make the code simpler, especially in a language with good data structures and algorithms (C++ is a shining example.)
Re:New Grad vs. Senior Dev by monocasa on Saturday March 28, 2020 @01:25PM (#22712631)
What if you have a large number of small N lists to be sorted?
Re:New Grad vs. Senior Dev by monocasa on Saturday March 28, 2020 @01:24PM (#22712619)
Eh, bubble sort can be quicker than q sort for samll values of N for instance.
Re:New Grad vs. Senior Dev by GuB-42 on Saturday March 28, 2020 @09:46PM (#22715702)
I am always uncomfortable with high "big O" algorithms. For example I know that with the data we have now, O(n^2) is fine, but if there is no strict bound on n, we don't know how far n will go in the future. It may also be a vulnerability, where the attacker uses data that is designed to exploit the worst case scenario.

It is more about peace of mind. By using the more efficient algorithm (by asymptotic complexity), I know that my code won't become a bottleneck. That's like using "size_t" instead of "int" in C. I know my array will not exceed 4GB in any practical application, but by using size_t, I know it won't crash if it happens one day. One less thing to worry about.

Almost all well designed libraries use hybrid approaches, switching from an algorithm optimized for low level efficiently for low N to a theoretically more efficient algorithm for high N. For example a sorting algorithm can go from insertion sort (good for low N) to quicksort (very efficient most cases) to merge sort (guaranteed nlog(n), highly parallelizable).

Re:New Grad vs. Senior Dev by tmpz22 on Saturday March 28, 2020 @02:06PM (#22712985)
And they never factor in training or maintenance level complexity, i.e. your ball of mud runs fast but have fun teaching ~5 juniors how to use it two years from now.
Re:New Grad vs. Senior Dev by michaelchisari on Sunday March 29, 2020 @06:41AM (#22717852)
This is key. If the number of objects processed will never be large, then it makes more sense to write a quick, easily understood O(n^2) loop in under a minute and move on.

Taking an extra 30 minutes to an hour or longer to optimize and test for large inputs that will realistically never exist is a waste of time and money.

If you feel that the value of N might, in some strange and rare combination of success and changed requirements, exceed the expected amount, add a check for the lowest value that may signify a problem and throw a warning.

  if N > 1000:
    debug.warn("N count of %d may be too large for existing algorithm. Consider optimizing.", N)
Leave it at that and get on to more important things.
Re:New Grad vs. Senior Dev by gorloth on Saturday March 28, 2020 @02:03PM (#22712959)
Taking the difference between normal complexity and asymptotic complexity to the extreme you have https://en.wikipedia.org/wiki/Galactic_algorithm which do have the best asymptotic performance, but only on values of n so large they never come up in real life.
Re:New Grad vs. Senior Dev by loosetypes on Saturday March 28, 2020 @01:05PM (#22712454)
Complexity yes, but I feel scalability is similarly a word with a misleadingly narrow connotation in practice.

Is an approach dependent on swathes of training data truly scalable if it doesn’t work for the first n attempts?

Re:New Grad vs. Senior Dev by gok on Saturday March 28, 2020 @05:53PM (#22714599)
It's mostly a shibboleth to make sure you actually did the coursework on your resume.
Re:New Grad vs. Senior Dev by samfisher83 on Saturday March 28, 2020 @12:04PM (#22711944)
When you do big O analysis you get best case, worst case, and average case. You have to do some thinking about the structure of you data when doing big O analysis.
Re:New Grad vs. Senior Dev by TeMPOraL on Saturday March 28, 2020 @12:18PM (#22712081)
It's not that. Something not properly covered in CS courses is that very often, performance is dominated by things that are not evaluated as a part of big O analysis. Like, memory allocations, cache friendliness, and other constant factors.

For example, according to the theory, a hash table is much better suited for key lookup and random additions than a vector. In practice, if you're storing a couple hundred elements, a flat array (with objects stored directly) will be faster because of data locality. If your problems are mostly "do a lot of small N ops" and not "do some large N ops", then big O analysis isn't all that useful anymore.

Re:New Grad vs. Senior Dev by seanmcdirmid on Saturday March 28, 2020 @12:48PM (#22712322)
This is covered in computer architecture, at least, and sometimes (but not often) in compilers.
Re:New Grad vs. Senior Dev by samfisher83 on Saturday March 28, 2020 @08:21PM (#22715349)
That is taught in your compilers class.
Re:New Grad vs. Senior Dev by saagarjha on Saturday March 28, 2020 @12:13PM (#22712028)
No, the point here is that big-O analysis means nothing if n is small. If n < 10 your algorithm could be exponential and still do better than a linear algorithm with a constant factor a thousand times larger.