<klange>
This code is awful and spends most of its time building strings through concatenation. I optimized common cases and got things down from over a second, and then for a final boost turned off the gc.
<clever>
some languages do string concat in a rather poor manner, copying src-a and src-b into dest
<clever>
so a + b + c, winds up copying (len(a)+len(b)) * 2 + len(c) bytes
<klange>
We kind have to do that here with how immutability of strings works, but I was able to make some key optimizations based on knowing the two strings were already vetted by the VM and complied with invariants.
<klange>
It now spends the majority of the time doing the memcpy.
<moon-child>
no rope?
<clever>
if you have immutable strings, then that makes stringbuilder stuff far simpler
<clever>
dont actually concat, just make an array of every string part
<klange>
Too many fundamental invariants built on being able to refer to strings as blobs of utf-8.
<clever>
yeah, you would defer the copy until something wants that
<klange>
And yes, this would almost definitely be faster if it was built on using an array and then combining that - str.join() is much better optimized.
<clever>
so `a + b` returns a list of `[a,b]`
<clever>
and when it becomes `a + b + c`, its just `[a,b,c]`
<clever>
and only if you (a+b+c).toUtf8(), do you then do one copy, of all 3 parts
<klange>
(or just... don't combine it at all, the obvious optimization is to stop trying to recombine the strings and instead just dump them directly and let the buffered io do it)
<clever>
but thats kinda mutable
<clever>
where its converting from an array of strings, into a string
<klange>
But I want to keep this as a fairly pure port of the original garbage code, so I'm not going to rewrite any of it.
<clever>
functionally no change, but it is mutating
<moon-child>
clever: I mean, this is clearly converging on ropes. Because what if you say a + b + c + d + ... + z
<clever>
moon-child: yeah, i was thinking that any time you do string concat, just return an array of strings wrapped in a special string-like type
<klange>
Yes, an array of strings of potentially different lengths is basically a rope. And turning that rope into a single string is much more efficient than a = a + b, a = a + c, a = a + d...
<clever>
and only when somebody wants a utf-8 blob, do you actually concat
<clever>
exactly
<moon-child>
klange: no, rope is a tree structure
<clever>
the nix interpreter has a concatLists function, for the same reason
<klange>
a tree structure that represents that, but better :)
<moon-child>
yeah
<moon-child>
also gives you logn random access
<clever>
ah, yeah, a tree could also help there
<clever>
t = [a,b]; result = [t,c];
<clever>
each time you concat, you refer to the previous array, and the new part
<clever>
and resolve that mess later
<clever>
otherwise, your having the same problem, copying the list of string pointers
<moon-child>
yes but a rope is balanced
<moon-child>
which is what gives you the logn random access
<klange>
I did two things to improve this situation. One was I realized I was actually doing a full scan to convert codepoint offsets to indexes for str[n] so I could copy utf-8 bytes, but that is utterly stupid of me.
<klange>
So that got switched for direct indexing into the codepoint array and then converting the single codepoint to the utf-8 bytes.
<klange>
(strings in Kuroko normally store utf-8 and lazily store "whatever is the simplest for individual codepoint access", which code be ASCII, "UCS-1", UCS-2, or UCS-4)
<clever>
a similar problem occurs in php
<klange>
(and if its ASCII it's a noop)
<clever>
when you do "a string with a $variable"
<clever>
the parser turns it into a mess of "a" + "string" "with" + "a" + $variable
<clever>
which incurs the same concat costs
<clever>
and the parser is dumb, that also occurs with "a string containing no vars"
<moon-child>
lmao
<moon-child>
I would expect nothing less from php
<clever>
but 'a singlequoted string' lacks $var support, so the parser doesnt do that
<klange>
The other thing I did was for concatenation I added a 'backdoor' string allocation function that takes the invariant metadata the normal function would calculate itself.
<clever>
so 'strings' are faster then "strings"
<clever>
moon-child: the issue is the lack of look-ahead, or back-patching in the parser
<klange>
Basically normal way of making a "KrkString" was "here's n bytes of utf-8" and you got to choose either "you can have it" or "make a copy, I don't own it".
<moon-child>
clever: well. It wouldn't be _so_ bad, if there were an optimizer. Then it could constant-fold "a" + "string" into "astring" etc.
<clever>
moon-child: yeah
<clever>
i dont know if php has improved since i read that blog
<klange>
And that would calculate the hash (full scan, kinda slow), check the intern table (fast, it's a good hash table implementation), validate the string is valid UTF-8, count the codepoints, and determine what storage format will be neceessary for direct codepoint indexing...
<klange>
Now there's krk_takeStringVetted where you pass it the hash, codepoint length, and codepoint storage type.
<klange>
So for concenation you can take the hash of string A and extend it with the contents of string B, which is faster especially for the "single character added to long string" case.
<klange>
You can combine the codepoint lengths of the two strings instead of having to check again.
<klange>
And you can set the storage type to the maximum of the storage type for the two strings.
<clever>
yeah, if you choose a hash algo where you can compute hash(a+b) from hash(a) quickly
<sortie>
(or otherwise do things that are technically allowed by the standards but I'm the only one doing it)
<heat>
klange, sadly I don't have a GUI and I think it might be a bit hard to do that with the tty
<heat>
maybe next year
<klange>
sortie: `off_t` section says `gid_t`
freakazoid12345 has quit [Ping timeout: 256 seconds]
<sortie>
Whoops fixed
<sortie>
64-bit pid_t is one of those things that sound good on paper but will get you chased out of town by a justified angry revolution
<sortie>
No PATH_MAX limit as well
<klange>
no mortal being should ever be allowed to run that enough processes at once for 64-bit pid_t to be useful
<sortie>
In brighter news, Sortix doesn't recycle pids, literally just ++'s
<sortie>
Constant time algorithm yo
<sortie>
PID_MAX processes is enough for everyone
<heat>
no backwards compat? booooooooooo
<heat>
i like my unixes crufty
<klange>
I am currently not recycling... toaru32 used a pid bitmap and would cycle back around when it overflowed, but, uh... I didn't copy that over in misaka
<heat>
i'm also not recycling but it's not a problem because my system doesn't usually boot for too long
freakazoid343 has joined #osdev
mahmutov has joined #osdev
freakazoid343 has quit [Ping timeout: 256 seconds]
* kazinsal
bashes his head against a cisco-shaped wall
<kazinsal>
this database schema is just awful
<sortie>
Btw that completes my trilogy of documentation for porting stuff :)
<sortie>
And then finally portability(7) with standard library details on portability issues
<sortie>
It's not merged to master just yet, still finishing it up, but the new ports system is live in staging/volatile and it's soo much nicer than the old method of huge tarballs checked into a couple hellish git repositories
<sortie>
Finally I have my BSD-style ports system :)
<sortie>
Sortix is really on a long road gradually transforming from a GNU&Linux like thingey into more of a BSD-like thingey
<klange>
can i be macos
<sortie>
toaruOS
<klange>
'shiny gui and a whole user experience out of the box, and i guess you can get other software, you heretic'
<sortie>
:D
<klange>
I don't want to put too much effort into having a solid infrastructure for ports _because_ I think it undermines the effort of providing things up front.
<klange>
Also because I have a package repository.
<klange>
Figure it out once and plop the binary on a server!
<sortie>
Curiously my ports system kinda defies the BSD model of you building your own binary packages
<sortie>
The whole system rebuild includes all the ports and makes all the binary packages, which go into the .iso and also on the release directory
<sortie>
The experimental package management lets you download & install ports using 'tix install foo' if you happened to not have loaded them via the bootloader
<moon-child>
klange: you worked on macos, right?
<klange>
technically
<moon-child>
sortie: bsds usually have binary packages too
<sortie>
moon-child, yeah, more meant that people aren't really supposed to build their own, though they can (although it's tied into a whole system rebuild)
<sortie>
E.g. BSD has a concept of flavors and lets you override a bunch of stuff, I don't really
<sortie>
I really do a lot of 'a whole user experience out of the box' actually since all the ports are included as part of the system, even in the main git repository instead of a secondary ports repo, and it's really a first class concept
<sortie>
Compared with BSD where the base system is self-contained and the ports system is an optional addon
<sortie>
The coolest thing with the my new ports system is that you can literally just “cd /src && make” OUT OF THE BOX and it'll natively rebuild the whole system including every single port :) (* If you have 3 hours to spare and enough (ram) disk space)
<sortie>
I don't think any other system has made development that easy :)