[edit]

For context—because Kozuma deleted it—he claimed that I blocked him. You see, he lashed out like a child at my libraries, which is what he does when he gets upset. This image was a refutation of that claim, because I do not block people.
Your libraries need fixed, worry about that and not the fact everyone has you blocked lmao.
In response to Kozuma3
Kozuma3 wrote:
Your libraries need fixed, worry about that and not the fact everyone has you blocked lmao.

Daily reminder that I'm open to bug fixes and optimizations for my libraries from any competent programmers. 😊😊😊 Two examples appear to be on this thread. One is OP and the other doesn't have "k" in their name 😊😊😊
In response to Popisfizzy
Popisfizzy wrote:
Daily reminder that I'm open to bug fixes and optimizations for my libraries from any competent programmers. 😊😊😊 Two examples appear to be on this thread. One is OP and the other doesn't have "k" in their name 😊😊😊

There's the immaturity, I'm simply trying to give optimization advice that works while you've been nothing but instigating.

That's why I have more fans than you AND I got me a starboi
Fellow starboi here.

It looks to me like he took your idea, replicated it, and applied it, and then noticed that it was less efficient.

Spell it out for us lesser-tiered mortals. Why is your way logically better, but in practice... isn't?
In response to Spevacus
Spevacus wrote:
Fellow starboi here.

It looks to me like he took your idea, replicated it, and applied it, and then noticed that it was less efficient.

Spell it out for us lesser-tiered mortals. Why is your way logically better, but in practice... isn't?

It's one less variable to initialize per call, removing i and using . will also save another variable declaration.

Doing so should improve things as you're saving the resources and re-using already declared variables.

It has ALWAYS worked that way, but you wouldn't understand that lower-tier starboi.
In response to Kozuma3
Kozuma3 wrote:
Doing so should improve things as you're saving the resources and re-using already declared variables.

Yeah but... In Fizzy's test, it didn't. Then you blamed the library, but that has no bearing on the actual sorting itself. It's not like it's creating a bunch of objects we have no idea about, it's just creating garbage data. Data that he's also posted post-sort.

You're right. Logically, not allocating resources to create variables should increase its speed, but it doesn't in this instance because the change in question is very smol.

Fizzy's criticism, then, is that your change isn't largely significant.

I think you got caught up in the idea that he was personally attacking you when realistically he was attacking your change. Additionally, when you went to refute his claims about how your change was smolboi impact, you didn't exactly show any proof for how his library was inefficient (which isn't really relevant) and went straight into "get on my level." Y tho
In response to Spevacus
Spevacus wrote:
Fizzy's criticism, then, is that your change isn't largely significant.

Are you dumb?

The OP clearly asked for advise on how to make it faster, and I did, whether it helps a little or a lot is still an optimization.


I always shave my butthole before I go for a swim. Don't want those hairs ruining my hydronamics and dragging me down. Some people say it's more about the technique and endurance training, but really it's all about the asshole.
Alright, so the goal is to question why everyones code works and to explain it in 8 pages. It doesn't matter if it's a single line of code. explain. Gotcha.

How did you know that I didn't know that his library didn't work? Are you assuming and if so how
In response to Kozuma3
Kozuma3 wrote:
Alright, so the goal is to question why everyones code works and to explain it in 8 pages. It doesn't matter if it's a single line of code. explain. Gotcha.

You're blatantly misrepresenting what I'm saying.

The change you made is insignificant because there is next to zero perceptible difference in testing even when stressed. That's the criticism.

When I say:

Spevacus wrote:
You're right. Logically, not allocating resources to create variables should increase its speed

I mean to say that it SHOULD. But in...

Kozuma3 wrote:
with practice you'll notice them

it doesn't.

Kozuma3 wrote:
How did you know that I didn't know that his library didn't work? Are you assuming and if so how

I never said that. What I said was that his library has next to no bearing on the test he did. Even if it DID, you never showed why it would. If he's wrong, show him why. Claim, evidence, assertion. Just like how he made the claim that your change wasn't better, made a test showing how, and then came to his conclusion.

I dunno where you got:
Kozuma3 wrote:
the goal is to question why everyones code works and to explain it in 8 pages. It doesn't matter if it's a single line of code. explain. Gotcha.

or
Kozuma3 wrote:
How did you know that I didn't know that his library didn't work?

It's almost like you're
Popisfizzy wrote:
grasping at straws
In response to Popisfizzy
Popisfizzy wrote:
The code is as follows. I use my MersenneTwister library to generate 100,000 floats. I do this because, unlike BYOND's built in RNG, my library will consistently generate the same sequence of floats across computers given the same seed. This keeps the test data consistent.

You've piqued my curiosity. In what way is the RNG failing to be consistent? I implemented the Mersenne Twister on the backend so the RNG should be the same, except in projects that were compiled prior to the change which use the old RNG.
In response to Lummox JR
I'm going completely off the documentation for rand(), which says that the RNG is hardware specific. I assume if it's MT then that might be out of date.

[edit]

It's actually in the documentation for rand_seed(), not rand():

The reference says:
The pseudo-random number generator is system dependent, so do not expect the sequence generated from a particular seed to be identical on two different machines or operating systems.
In response to Popisfizzy
Popisfizzy wrote:
I'm going completely off the documentation for rand(), which says that the RNG is hardware specific. I assume if it's MT then that might be out of date.

Ah, I think that is out of date then. I'll make a note to change it. Internally BYOND has used Mersenne Twister for its RNG for some time, at least for soft code. I'd like to also eventually add a way for users to setup their own random state objects that could be used independently of one another.
Thanks everyone for your input.

I think taking the the variable out of the loop is slower (as PIF showed) because a for loop with a var definition is such a common thing that the compiler is good at optimizing it. I had no idea using the . var as a variable was slower. Perhaps the code would run faster if that was avoided. (One less reference copy? EDIT: No difference.)

If anyone is interested, here's what I used for testing:

I found in testing, that if you do something where you create a list of values and then call each sort proc line-by-line (on copies of the list) instead of looping through them, that they would take more or less time depending on the order they were called. My guess is this has to do with the way the memory is managed.

I fixed this by using a list of procs, i.e., list(/proc/Sort1, /proc/Sort2, /proc/Sort3). Then I used rand_seed to ensure the same list of values and used call to call the procs.
world/fps = 60
proc/CheckSorted(list/L, start = 1, end = 0)
if (end == 0)
end = L.len + 1
for (var/i = start, i < end - 1, ++i)
if (L[i + 1] < L[i])
return 0
return 1

var/randSeed = 1234
mob/verb/TestSort()
var/list/testProcs = list(/proc/Sort11, /proc/Sort12, /proc/Sort13)
for (var/P in testProcs)
src << "."
sleep(1 / 6)
rand_seed(randSeed)
for (var/j = 1 to 100)
var/list/L = new
for (var/i = 1 to 999) // these numbers can be modified
L += rand(0, 10000)
try
L = call(P)(L)
catch (var/exception/E)
world << "<font color=red>Error: [E.name]"
world << "<font color=red>[E.file] ([E.line])"
return
if (!CheckSorted(L))
world << "FAILURE"
++randSeed
src << "Done!"

I would change out which procs I was testing as I came up with new optimizations to test.

Another note anyone may find interesting is that, I also tried to do an in-place version of the merge sort (and I also tried quick sort), and it was slower. It seems doing any list operations that operate on anywhere other than the front or back of the list are slow. (Which makes sense, because of how linked-lists are implemented.)
Using the . var seems to have some overhead, removing it is a slight optimization.

Here is the current fastest version:
proc/Sort(list/L) // requires operator<, stable
if (L.len <= 1)
return L
if (L.len <= 5) // bubble sort for small lists
var/swaps = 1
while (swaps)
swaps = 0
for (var/i = 1, i < L.len, ++i)
if (L[i + 1] < L[i])
L.Swap(i, i + 1)
++swaps
return L
// merge sort for large lists
var/pivot = 1 + round(L.len / 2)
var/list/L1 = .(L.Copy(1, pivot))
var/list/L2 = .(L.Copy(pivot, L.len + 1))
L.Cut()
while (L1.len && L2.len)
if (L2[1] < L1[1])
L += L2[1]
L2.Cut(1, 2)
else
L += L1[1]
L1.Cut(1, 2)
L += L1
L += L2
return L

Note: It appears that round(L.len / 2) is faster than round(L.len * 0.5). Maybe the compiler detects integer operations and optimizes it. EDIT: Maybe it's detecting division by a power of 2, and converting that into a bit shift, actually.
(Also, I changed my test code to shuffle the list of procs before the tests to make the tests independent of order. Something I should have done from the beginning.)

EDIT: I tested bit shifting instead of division. There's a slight optimization there.
                     Profile results (total time)
Proc Name              Self CPU    Total CPU    Real Time     Overtime        Calls
------------------    ---------    ---------    ---------    ---------    ---------
/proc/Shuffle             0.000        0.000        0.000        0.000           20
/proc/CheckSorted         1.997        1.997        1.997        1.980         4000
/mob/verb/TestSort        0.674       40.622       40.970        0.668           20
/proc/SortBitShift       18.976      103.241      103.401       18.666      1022000
/proc/SortDivision       18.975      104.026      104.180       18.668      1022000

The fastest version is now this:
proc/Sort(list/L) // requires operator<, stable
if (L.len <= 1)
return L
if (L.len <= 5) // bubble sort for small lists
var/swaps = 1
while (swaps)
swaps = 0
for (var/i = 1, i < L.len, ++i)
if (L[i + 1] < L[i])
L.Swap(i, i + 1)
++swaps
return L
// merge sort for large lists
var/pivot = 1 + (L.len >> 1)
var/list/L1 = .(L.Copy(1, pivot))
var/list/L2 = .(L.Copy(pivot, L.len + 1))
L.Cut()
while (L1.len && L2.len)
if (L2[1] < L1[1])
L += L2[1]
L2.Cut(1, 2)
else
L += L1[1]
L1.Cut(1, 2)
L += L1
L += L2
return L
Page: 1 2