Welcome to the main channel on the development of MoarVM, a virtual machine for NQP and Rakudo (moarvm.org). This channel is being logged for historical purposes.
Set by lizmat on 24 May 2021.
00:02 reportable6 joined 00:36 MasterDuke joined
MasterDuke jdv++, the releases just keep coming like clockwork 00:37
jnthn, nine, etc: anybody have any thoughts about github.com/MoarVM/MoarVM/pull/1799 ? i'm not sure it's a good idea 00:46
03:18 MasterDuke left 06:00 reportable6 left 06:02 reportable6 joined
nine I'm a bit torn. Not a huge fan of the wasted memory. On the other hand it is somewhat limited. 06:57
Is there a cheap way to limit the required buffer size even more based on the number's value? 06:58
Since we don't mind if we're off by 1 or 2, a reasonably cheap way would be: MVM_malloc((64 - __builtin_clzll(i | 1)) / 3 + 1) 08:08
__builtin_clzll is available on gcc and clang and compiles to a single assembly instruction which counts the number of leading 0s (for the number 0 we don't get an answer, so | it with 1 to have always at least 1 bit set). Thus to get the number of the most significant bit set we subtract that from 64. 08:10
08:10 sena_kun joined
nine Divide that by 3 to get the rough estimate of decimal digits for this number of binary digits and add 1 to avoid the missing digit when the division rounded down. 08:10
For a comparison of the results with the perfect answer run rakudo -e 'say "{(2 ** $_).Str.chars} {$_ div 3 + 1}" for ^64' 08:11
Callgrind seems to indicate that this makes the code actually faster. But I'm not sure I interpret callgrind's output correctly. Haven't used it in years, so that may just be wrong. 08:12
However: this whole investigation made me wonder about something completely different: 08:13
There's a clear bias here. The smaller the number, the more often it will appear in real world scenarios. Even your benchmark uses just the numbers up to 10 million. Indeed the same is true in general: the shorter the string the higher the lightlyhood of it appearing. 08:15
MVMString stores strings in a variety of representations: MVMGrapheme32, MVMGraphemeASCII, MVMGrapheme8 and MVMStringStrand. They all have in common that the actual string data lives in a malloced memory area. 08:17
This can mean that for a stringified 3 digit number, we alloc just 3 bytes of memory and then store an 8 byte pointer in MVMString pointing at this tiny memory area.
Depending on the allocator this 3 byte area may actually waste 4 bytes of memory or even 8. 08:18
Since MVMString already has all the machinery to distinguish between those different storage types, why not introduce one more for short strings that stores the characters directly in the MVMStringBody instead of those pointers? 08:19
I.e. union { MVMGrapheme32 *blob_32; MVMGraphemeASCII *blob_ascii; MVMGrapheme8 *blob_8; MVMStringStrand *strands; void *any; MVMGrapheme8[8] chars; } 08:20
I think this fares even better as it avoids the costly division: int msb = 64 - __builtin_clzll(i | 1); char *buffer = MVM_malloc(msb >> 1 - msb >> 3 - msb >> 4 + 1); 08:35
Actually since it's just 64 input values, we could also just use a lookup-table. 09:14
09:18 sena_kun left
lizmat nine: this feels like an approach that Perl also uses internally for small strings? 09:23
I mean, the idea feels very familiar
nine Oops.... got my operator precedence wrong. Should be: char *buffer = MVM_malloc((msb >> 1) - (msb >> 3) - (msb >> 4) + 1); 09:33
Lookup-table seems to be the clear winner. It's most correct and also seems to be the fastest of the suggested options. Caveat being that correct handling of negative numbers is still missing (those will have lots of leading 1s instead of 0s) 09:47
m: (^64).map({(2 ** ($_ + 1) - 1).Str.chars}).join(", ").say
camelia 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20
12:00 reportable6 left 12:03 reportable6 joined 12:24 linkable6_ left 12:26 linkable6_ joined 16:59 sena_kun joined 18:00 reportable6 left, reportable6 joined 18:46 linkable6_ left 18:48 linkable6_ joined
japhb nine: I think a few years back someone (timo?) created a branch trying to do what you're talking about, including very short strings directly into the MVMStringBody. Sadly I don't know the branch name at this point .... 20:16
lizmat my $M := MoarVM::Bytecode.new("c"); 20:23
my %b is Bag = $M.map(*.name);
.say for %b.sort(-*.value).head(10);
set => 121516 20:24
dispatch_o => 108447
decont => 97621
wval => 79660
const_s => 61392
getcode => 60319
getlex => 32927
assertparamcheck => 25808
wval_wide => 25737
checkarity => 24944
bytecode introspection FTW
in the next release of MoarVM::Bytecode.... tomorrow 20:25
nine japhb: yeah I can't shake the feeling that this has been tried before and timo would be just the one to do that. 20:33
japhb: the branch is called in-situ-strings :) 20:34
Looks like exactly what I was thinking of including being able to store 2 grapheme32 in-situ (well I didn't have that word for it). Only thing it misses is using this storage format for "small" stringified numbers. 20:39
lizmat How big is the chance that a current MoarVM would be able to run a precompiled file of an older MoarVM? Would that even happen nowadays? 20:55
asking because it feels like the DEPRECATED opcodes could be removed
or at least, recycled
[Coke] IIRC, they have been recycled in the past. 20:56
I think when you bump the bytecode version number. 20:57
(is a point when it can happen)
20:57 MasterDuke joined
MasterDuke ++nine for grant 20:58
[Coke] but IANAMD
lizmat doctor? 20:59
MasterDuke i was also trying to find the in-situ-string branch and couldn't remember the name and found this instead github.com/MoarVM/MoarVM/tree/shor...ring_cache
might make sense also 21:00
[Coke] moar develoer
lizmat hehe
afk& 21:01
MasterDuke timo1: any memory of the state of those branches? how much work would they need before ready to merge to main? 21:03
21:29 sena_kun left

Powered by Cro and the Raku® Programming Language.

Please report any issues / comments / feature requests as an issue on App::Raku::Log.

Thank you!