boomerBummer

[u/zomreddit]

[u/navetzz]

The largest in size this data structure will ever get is 12.

[u/FUTURE10S → u/navetzz]

A genuinely good reason to be O(n² ) tbh, naive and fast on tiny data structures beats out intelligent but with a lot of setup

[u/Terroractly → u/FUTURE10S]

Yeah there's a lot of algorithms that have a relatively high amount of fixed cost compared to simpler and technically slower algorithms.

For instance one algorithm may have a runtime of n³ ms but the "superior" one has a runtime of (n² + 1000)ms.

In this case the naive approach will be faster for any n<=10

[u/Superb_Chemistry_906 → u/FUTURE10S]

My self diagnosed OCD would not let me do it even in that case.

[u/potatopierogie → u/Superb_Chemistry_906]

After 200 hours of work you get it down to O(n^1.9 )

[u/Superb_Chemistry_906 → u/potatopierogie]

You ever heard of nlogn? That's the basic cliche. Your "joke" is absurd. You seem to lack basic university education.

[u/Wesstes → u/Superb_Chemistry_906]

Something tells me you've only just passed the algorithm analysis class

[u/Superb_Chemistry_906 → u/Wesstes]

What is that "something"?

[u/potatopierogie → u/Superb_Chemistry_906]

You seem overly proud of knowing something literally everyone knows

[u/Superb_Chemistry_906 → u/potatopierogie]

Why did you then write that stupid O(n^1.9)? Seems like nothing better came to your mind. I have not ever heard of such case. Utterly dumb.

[u/potatopierogie → u/Superb_Chemistry_906]

I have never heard of something. If you have, you're dumb

Bro come on. You not ever hearing of something doesn't make anyone (but you) utterly dumb.

[u/FUTURE10S → u/Superb_Chemistry_906]

Cool, have a nlogn with a flat cost of 1000ns per each element, my n² with a cost of 10ns per each element and at 12 elements, I'll have 1440ns and you'll have 12950ns.

[u/Superb_Chemistry_906 → u/FUTURE10S]

I think that you just made up that flat cost difference assumption. In reality, it does not work like that, but rather it's about the overhead of the algorithm, while the flat cost is the same. And the claim that the input "will never be more than 12 items" is a typical one at the beginning of poorly optimized systems.

[u/Furyful_Fawful → u/Superb_Chemistry_906]

Merge sort is O(n log n), and it has a large flat cost associated with allocating O(n) additional space worth of sub-arrays. A naive implementation of merge sort would easily hit the flat cost as specified, while naive n² algorithms often rely on swap operations that are easily optimizeable by the compiler

[u/Valuable_Leopard_799 → u/Superb_Chemistry_906]

In that case you can try working on the switching version which checks the properties of it's inputs and chooses whichever is more suitable.

[u/Superb_Chemistry_906 → u/Valuable_Leopard_799]

I don't know - I just do not obsess about small inputs - they are small anyway. I think that the cases when optimizing for them is needed are very specific and I maybe even haven't come across them. It could be processing of a lot of small data records, but I haven't done such thing, I think.

[u/zkwarl → u/navetzz]

I actually hit that in production code once. There was a recursive binary search to find the nearest element in an array of sixteen sorted doubles. Converting to a linear search was about 10X performance gain.

[u/Neverwish_ → u/zkwarl]

Welp, binary search is not supposed to be recursive...

[u/Glass_Teach_2854 → u/Neverwish_]

Assuming comparisons aren't expensive, Binary search should be slower even if its not recursive for arrays that size. The book keeping will outweight the reduced lookups

[u/Neverwish_ → u/Glass_Teach_2854]

Yeah, no argument there. I was just pointing out that proper binary search should not be recursive.

[u/Zeikos → u/navetzz]

I had a data structure that was O(n!), got flack for it when it was impossible - there were guard clauses - for n to be higher than 3.

[u/evanldixon → u/navetzz]

If it will never be bigger than 12, it could be argued to be O(1). No one ever said how big 1 is after all.

[u/Vesuvius079 → u/navetzz]

And even 1000 would unnoticeable with what the inner loop is doing.

[u/neoronio20 → u/navetzz]

Then N = 12, O(144) == O(1)

[u/DeltaV-Mzero → u/navetzz]

Could be true if you use the right base

[u/MayorAg]

Wouldn’t you un-press the button?

[u/MRanse → u/MayorAg]

There were cases where the turbo button was inversed, so people had different experiences.

[u/Z3r0funGuy → u/MRanse]

Never experienced this.. the turbo buttons were originally a backwards compatibility feature to play nice with old software that was dependent on slower clock speeds.

[u/ArjixGamer → u/Z3r0funGuy]

That's weird, why would the playstation 2 have a turbo button then? It's a console with a curated list of games.

[u/Z3r0funGuy → u/ArjixGamer]

I just realized how young you are. We are having a discussion from two completely disparate points of view.
I’m with you, it is a weird word choice. Take it up with the marketing department.
If you really want to understand, look up “486 turbo button” for the history.

[u/ArjixGamer → u/Z3r0funGuy]

Regardless of my age, I grew up with old tech.

But not old enough to use VHS tapes or floppy disks. I still have my PSX with 2 controllers and a memory card. But all my DVDs are damaged.

I am 22 btw

[u/ekauq2000 → u/ArjixGamer]

This is the turbo button they’re referring to:

https://en.wikipedia.org/wiki/Turbo_button

[u/ArjixGamer → u/ekauq2000]

Oh yeah, I had that on my first pc, never used it.

[u/ih-shah-may-ehl → u/ArjixGamer]

There were plenty of games that dealt with time and clocks in weird ways. For example the old space quest games, which means that as computers got faster, some things became literally impossible because some in-game timers or counters elapsed in less time than needed to react to on-screen information.

[u/NullVal]

What DID those turbo buttons actually do?

[u/AdBrave2400 → u/NullVal]

I thought it was something for compatibility like for example games that would run at wrong speeds. Is that right?

[u/LuigiWasRight447 → u/AdBrave2400]

Yes that is correct

[u/rnzz → u/AdBrave2400]

for me it was to help me get past some levels on Moon Bugs, Jaybird, etc

[u/El_Mojo42 → u/NullVal]

It was actually to reduce the clock speed for compatibility reasons. Turbo was the normal speed. 

[u/Nebula_Wolf7 → u/El_Mojo42]

This, because the physics and other graphics were tied to the frame rate, reducing the clock speed made older games run normally

[u/Quicker_Fixer → u/NullVal]

https://giphy.com/gifs/av2qAouzcA70A

[u/LuigiWasRight447 → u/NullVal]

It increased the cpu clock speed because for video games the speed of the game was tied to the framerate for the longest time and even to this day youll sometimes see games like that on consoles. Like the physics engine in fallout for example. So if youre game was running to slow turn on turbo. Too fast? Turn it off.

[u/KawaiiMaxine → u/LuigiWasRight447]

It actually reduced the clockspeed to a specific common speed for compatibly

[u/Xlxlredditor → u/KawaiiMaxine]

To the crisp 4.77Mhz of the original 8088 of the IBM PC!

Edit: thanks u/JustSomeRandomCake fire the additional 770 kilohertz

[u/JustSomeRandomCake → u/Xlxlredditor]

4.77!

[u/Xlxlredditor → u/JustSomeRandomCake]

Shit I forgot 770 kilohertz, edited

[u/LuigiWasRight447 → u/KawaiiMaxine]

Oh i guess i got it backwards. That makes sense though. Im a little to young to have ever used one of those pcs so im just going off what ive heard

[u/G3nghisKang → u/LuigiWasRight447]

for the longest time

Shit PC ports will still slow down when the framerate gets too low

[u/Attileusz → u/G3nghisKang]

Tying framerate to simulation rate has advantages like everything being deterministic, if you press a button on frame n you'll get the same frame n+1 visually no matter the framerate. In this configuration you gotta cap the framerate or interpolate two frames (but this causes visuals to have a 1 frame latency over gamestate, this may or may not be fine for some games). It's a perfectly valid way to make a game IF your game is known to be optimised enough to run at at least simulation speed on supported hardware.

I'm not talking about tying time to clock cycles here, that's a dead paradime. We simply yield to the operating system and request that it schedules the program again when the next simulation tick needs to be computed and/or when the next frame needs to be drawn (usually called sleeping).

[u/LawfulnessDue5449 → u/NullVal]

Turns on a machine that takes the exhaust air to spin a turbine that will compress air on the other side

[u/zomreddit → u/NullVal]

I think placebo effect

[u/4Floaters → u/zomreddit]

You weren't supposed to hold it down it was for quick boosts - joke

According to Wikipedia the turbo button allowed the computer slower for compatibility with older applications

[u/sebjapon]

When I was in a Master course, my professor just told me: who cares about speed, Moore’s law will do that work for us.

So the answer is: wait 2 years, buy a new CPU/GPU and it will run faster

[u/Superb_Chemistry_906 → u/sebjapon]

I think Moore's law has been dead for some time - the main way to increase performance is just put more watts into it.

[u/sebjapon → u/Superb_Chemistry_906]

Yeah my story is 15 years old though. At that time it made sense

[u/GenericFatGuy → u/sebjapon]

And now we have a bunch of devs who don't know how to optimize.

[u/Superb_Chemistry_906 → u/sebjapon]

But even then, this story gives an answer to why, no matter how much faster HW got, the desktop experience was always a bit laggy, with another reason being the never ending urge to fill the performance potential with needless animations and effects.

[u/remy_porter → u/Superb_Chemistry_906]

The thing is, most of those animations and effects are pretty cheap computationally. Especially in the era of GPUs.

[u/Superb_Chemistry_906 → u/remy_porter]

Under this pretense, they are added up to conveniently cancel out any HW advances in order to keep computers annoying.

[u/remy_porter → u/Superb_Chemistry_906]

Except that’s just not true, is my point. Those animations are actually very cheap to render. They can make the system feel slower when they’re badly done, not because it actually hurts performance but because nobody wants to wait for your animation to finish.

[u/Superb_Chemistry_906 → u/remy_porter]

I have animations turned off and even then, when the system is somehow strained, it even takes some time for a window to get focus after a click. So every little thing adds up. And of course, animations are long and annoying, I agree.

[u/remy_porter → u/Superb_Chemistry_906]

That sorta makes my point: it’s not the animations that are causing performance issues.

[u/Superb_Chemistry_906 → u/remy_porter]

In the case of the strained system, animations make it even worse: they add more strain and turn even slower and more glitchier, making the PC experience even more annoying - so they are just pointless flashy thing which kick you in the ass in the hardest times.

[u/whackylabs → u/sebjapon]

My professor also told me: Ontogeny Recapitulates Phylogeny. So every time a new hardware system comes to life you need to start thinking in machine cycles all over again.

[u/FUTURE10S → u/sebjapon]

Throwing hardware at a software problem, a tale as old as time itself (and ngl it works pretty well)

[u/zomreddit → u/sebjapon]

I glued another Turbo button to the existing button and quadrupled the speed!

[u/Arclite83 → u/sebjapon]

I've enjoyed watching us "top out" though, first on single processors and embracing threading, then on nm size getting to the point where "gold atoms are too big".

The high precision machines needed to make high end and quantum processing chips to the molecular precision they require are marvels of technology just themselves.

[u/HungryCaterpillers → u/sebjapon]

How long ago was that? Because even when I was in college, we had already approached the limit of Moore's law.

[u/2204happy]

Real ones know that the turbo button actually makes the CPU run slower.

[u/floatinggoateyeball]

decreasing N, obviously

[u/pabloramon044]

The turbo button that slows it down?

[u/GrandDukeNotaras]

So it runs in O(zzzzzztututututu) time 

[u/stupled]

So much nostalgia.

[u/glx0711]

I just reduce delay_ms(8); to delay_ms(5);.
To still have some room for improvement.

[u/RarerGiraffe]

If it works don't fix it. If it doesn't work don't tell me.

[u/_Repeats_]

I would profile the entire application and see if this algorithm was a hotspot. If not, move on to the next ticket.

[u/stormbringerelric77]

For real though, what did the turbo button actually do? And why wouldn't you want it on all the time?

[u/synchrosyn → u/stormbringerelric77]

Old games used the clock speed of the computer to determine certain things like enemy movement (move on every tick). But the Devs didn't account for newer CPUs having different clock speeds so the timing was completely wrong and games would act erratic. 

The turbo button actually slowed the clock speed to match the previous generation thus making games work again. 

You pressed it only when playing games because otherwise your entire system is slowed down. 

[u/ArjixGamer → u/synchrosyn]

Uhh, why would it be called turbo then?

Turbo implies it makes it faster, not slower.

Also, I remember my Playstation 2 controller had a turbo button.

[u/synchrosyn → u/ArjixGamer]

It is a marketing thing. It was called turbo so that people actually would press it. If they called it the "nerf" button nobody would ever press it even if they needed it.

Turbo also implies "only use it when necessary". The standard user would not understand why they need to slow their computer or use some sort of compatibility mode. The idea is that a standard user would think is "games need more power, let me press the turbo button, but I shouldn't waste my turbo otherwise". Or "oh I left turbo on, it is too much power for my other apps, I should turn it off". So people did the right thing, even if it was for the wrong reason.

The turbo button on your PS2 controller is a completely different concept and surely was a 3rd party controller. It lets you hold a button and it would button mash it for you, it had nothing to do with the system or performance.

[u/ArjixGamer → u/synchrosyn]

Now that you say it, yeah it might have been a 3rd party controller.

[u/slaymaker1907]

Easy, we’ll keep the inputs small

[u/BenadrylTumblercatch]

Change the rgb to blue and the wavelength of the code will be shorter

[u/Vesuvius079]

It works ok.  I don’t need to make it faster then.

[u/GoddammitDontShootMe]

I thought I heard pressing it in actually made your computer slower.

[u/CockyBovine]

https://giphy.com/gifs/lKXd9sYM5dI9W

[u/wu-not-furry]

Scratch programmers be like

[u/WeirdTie2290]

Software architects nowadays scale horizontally. Add 4x the hardware for 50% overall performance gain.

[u/iyamegg]

The 'DLSS will make it playable' argument backported to ye olde times.

[u/ofnuts]

Would also replace the SX proc by the DX version.

[u/Mr_DeWitt_]

The Turbo button was designed to slow down the CPU rather than increase its speed.

[u/Balahawka]

Turn it into O(2ⁿ⁾ because bigger number better

[u/seyy02]

I honestly thought the turbo button made it faster though 😂

[u/danf10]

Can confirm. Had a PC with a turbo button, and it indeed made it faster.

[u/TapRemarkable9652]

ddr7