@wizzwizz4 I missed that you were handcoding asm!

@fomin Badly. It keeps crashing.

@wizzwizz4 ah... Is it asm in C?

I just added timing info to the question

the C++ code is amazingly fast

@fomin In Rust.

You wanted a Rust solution. :-p

cool!

can any rust people help?

there is #rust on freenode for example

1. write a C++ solution 2. compile to assembly 3. embed assembly in rust 4. profit!

@thedefault. your code is fast!

and has almost 0 system time reported by time

@fomin Probably not; it's Linux kernel calls I'm struggling with.

@wizzwizz4 hmm.. there are a lot of linux kernel people in the world too

@wizzwizz4 what about them?

@ngn They don't work if you don't set the registers right.

@wizzwizz4 maybe a MWE?

or a M not-W E :)

@ngn your code is fast too :) Just not fast!

any luck with the automata?

@wizzwizz4 they use the same registers as regular function calls except that rcx is replaced with r10

@ngn Oh, really?

That makes it trivial then!

Thanks.

ngn FTW!

@fomin yes, it works but 10x slower right now. i'll optimize it today.

cool!

@wizzwizz4 at least on x86_64 linux

@ngn Is that the third argument?

@wizzwizz4 fourth

@ngn How wrong is this code?

unsafe fn writev(iovecs: *const iovec, count: usize) {
    asm!(
        "syscall",
        in("rax") 20u64,
        in("rdi") 1u64,
        in("rsi") iovecs,
        in("rdx") count,
        options(nostack)
    );
}

I sometimes wish that bounties could last two weeks

@wizzwizz4 i don't understand everything there, but if you don't use syscalls with 4+ args (like mmap for instance), you can get away with just 1 line of code

@ngn Am I using the right registers?

Assuming it actually puts things into those registers, which it doesn't.

just a moment, i'll show you one way to do it

@ngn The syscall number is 20 and there are three arguments. rdx is for the third argument?

@wizzwizz4 damn.. i can't read. yeah, looks right.

Does the normal calling convention for functions populate rax?

I want to abuse it.

@wizzwizz4 no, it uses it only for the result. but you have to tell the kernel somehow which syscall you want, so it uses rax

Urgh, so I still have to populate rax myself, which I can't work out how to tell the compiler to do.

Oh well.

@wizzwizz4 see this fragment

M2(x) is defined here

@wizzwizz4 and here's another easy way to do the syscalls

@wizzwizz4 btw, do you really need writev()? the output is so small (less than 1<<28) you can use a statically allocated buffer and shoot it out with a single write()

@ngn I was planning on starting a second thread and outputting in parallel.

This assembly should work, right?

_start:
 mov     rdi, rsp
 call    main
 #NO_APP
 ud2
main:
 mov     eax, 56
 xor     edi, edi
 #APP
 syscall
 #NO_APP
 ud2
rust_begin_unwind:
 ud2

But I just get SIGILL.

@wizzwizz4 you could ask on SO too. Although this is the best chat room :)

@Anush Use the Q&A functionality of a Q&A platform‽

@wizzwizz4 depending on flavour of asm this is, you might need a $ before constants like 56

what is "ud2"?

@wizzwizz4 it's all idea :)

@ngn I think it's an invalid instruction to stop things running off the end of their functions and smashing other stuff up.

> Generates an invalid opcode exception. This instruction is provided for software testing to explicitly generate an invalid opcode exception. The opcode for this instruction is reserved for this purpose.

hjlebbink.github.io/x86doc/html/UD2.html

Please post the link here if you do ask on SO

I am very interested

@wizzwizz4 are you sure you want syscall 56? it's clone()

@thedefault. Now I am I intrigued what timing you would get from edit distance 3. Did you try it?

@ngn Not at all.

That would explain why I keep getting a new thread just before it crashes.

you probably want exit(), number 60

@Anush My approach doesn't really generalize to other edit distances

@thedefault. Oh how come?

@ngn That worked! Thanks.

yay :)

Ooh!

Now all I need to deal with is the fact I'm using argc as argv[0].

@Anush well, I could just wrap dist2() in a loop, but then it'll produce many duplicates (and thus it won't have a significant advantage over ngn's answer)

@wizzwizz4 why not just read() the input?

@ngn Slightly slower.

@Anush and there will probably be far too many lines for me to calculate how many duplicates it produces (I expect at least a billion different lines)

@wizzwizz4 ok. you know argv[0] is the executable itself? the first arg is argv[1]

@ngn Only by convention.

hah, true :) but you'd have to explain this to the OP who'll do the testing..

Did you know that pointer hackery in Rust is undefined behaviour?

The compiler's optimising away all my pointer dereferences.

i don't know rust

Imagine C++, but it usually makes more sense.

from what i've seen, it's too verbose for my taste

@ngn Hah :)

Did anyone consider multi thread? I think all the answers use one core currently

@wizzwizz4 is your code working now?

@fomin Yeah, but it only prints argv[1].

@thedefault. You make me want to write a separate question for larger edit distances now :)

@wizzwizz4 progress! :)

@thedefault. I think you get around billion strings without duplicates for edit distance 3. My python code can compute it exactly for a given input string

@fomin The bottleneck is probably output for most people.

@wizzwizz4 it is piped to dev/null

Oh I added user and system in my timing

You still have to do it. The kernel can't output to /dev/null in parallel, afaik.

Maybe it can, which would change my answer.

I saw what you mean

It's a nice question!

It must be possible otherwise when you have 64 cores running independent processes they would wait for each other

Which is bad

Oh, it can definitely output in parallel through different file descriptors.

But we're meant to output to stdout.

The question doesn't exactly say that :)

You could ask the OP :)

Oh, that's really cheaty.

Are all Code Golf standard I/O methods allowed?

What are they?

CMC: Given a date on the Symmetry454 calendar, return its day of the week. Remember that abuse of I/O formats is a standard loophole.

@fomin if you output to multiple files, the output is out of order so

The order is not important . This is in the question

@ASCII-only ^^

@thedefault. I fixed the typo with the count number. Thank you for spotting that

I've got a solution that takes a few nanoseconds.

@fomin either way i don't believe multiple files is a valid output format

@ASCII-only got you. How about if I allow it?

@wizzwizz4 does it do nothing? :)

@fomin Not quite nothing – but close enough.

why, it can return a pointer to a function that produces the strings when invoked repeatedly, if you prefer that :)

It binds a closure over a generator.

Pointer to function, pointer to state.

Let's stay kosher :)

@fomin the kosher thing to do is to do nothing, at least today :)

(it's saturday)

@ngn :)

@wizzwizz4 is your code still stuck with the asm?

@fomin I'm not sure what you mean.

I've nearly got forking working.

Cool!

@wizzwizz4 it was just crashing not long ago

Ah, yeah, it no longer crashes.

Turns out that I was adding 8 * 0 bytes instead of 8 * 1; it wasn't optimising out my pointer offsets.

what if we can detect if stdout is /dev/null and do nothing only in that case? :)

@wizzwizz4 cool

@ngn that is the sort of thing Uber do

On an unrelated note, echo 2 | sudo tee /proc/sys/vm/overcommit_memory can straight-up disable malloc if you don't have any swap.

This makes the computer have a fun time with the flashy lights.

That's very interesting

My Linux box freezes if I use more than 50% of RAM for some reason

Sounds like the same issue.

Check out man proc.

Will do

Did turning off swap work for you?

Well, it did something.

:)

You've heard of racing the beam.

Now it's time for racing the kernel.

My new plan: hand the kernel a data structure to print, and hope I can populate it faster than the kernel processes it.

hey, look - only 2 syscalls:

$ strace ./a.out abcdefghijklmnop >/dev/null
execve("./a.out", ["./a.out", "abcdefghijklmnop"], 0x7ffe81ceab28 /* 44 vars */) = 0
write(1, "  abcdefghijklmnop\n  bcdefghijkl"..., 85190086) = 85190086
exit(0)                                 = ?
+++ exited with 0 +++

Nice.

Padding with spaces is a really neat idea.

@wizzwizz4 padding? those are inserted 0x20-s

from the challenge: "The characters are taken from the 95 printable ASCII characters, byte values 32 (0x20) to 126 (0x7E) ( to ~)"

@wizzwizz4 I can dd if=/dev/zero of=/dev/null bs=2M at 21 GB/s, so I guess it's going to be hard (because the kernel somehow handles at least 42 GB/s of IO)

Is this really where most of the time is spent? The C++ solution is faster because it cleverly makes fewer duplicates....I think

@thedefault. It cheats; it allocates a page of zeroes, then discards it, but never actually needs to make any zeroes.

@fomin The C++ solution makes even fewer duplicates.

I meant c++, sorry

It just looks like C :)

"ngn's revenge" (the new solution i'm working on) makes no duplicates, but could still end up slower

My plan is to bide my time until somebody's found the fastest algorithm, then clone it fasterer.

it might, I only make around 1 duplicate in 1000 strings on abcdefghijklmnop, so it is now mostly about speeding up file IO (or are you using multithreading?)

That wasn't my original plan, but realistically I'm not going to get this finished until right near the end. :-p

@thedefault. me? no, not multithreading

@ngn I look forward to it!

I replaced my time-based profiler by manually stopping the program in gdb and looking at the instructions, and, indeed, it seems like most of the time is spent on IO (to be specific, on writing strings to unaligned addresses in the buffer, not on the fwrite system call).

And not being able to read the code :)

@thedefault. hmm..can the alignment issue be addressed in any way?

can we write some empty lines or null bytes? :)

@wizzwizz4 an awesome last second win :)

@thedefault. yes. You just have to have the strings somewhere in there with separators

@fomin can we use '\0' as separator? if yes, i think you should mention that in the challenge

Hmm

I worry about what is going to happen

I would prefer a standard separator

ok

@fomin the option to output empty lines could be worth mentioning too

I wonder whether a GPU would help.

sounds really unlikely to me

is anybody else working on a solution with finite automata?

@ngn good point

I feel rather foolish now; I've just realised you don't need any memory copies.

I now output many empty lines, padding all strings to the same length (I tried 20 and 24). I got the profiler to output the timing for specific instructions, and the top 3 instructions are still in 3 different inlines of printbuf, where the strings are copied to the buffer :(

Pretty cool

Well that's a new one:

error[E0080]: it is undefined behavior to use this value
  --> src/main.rs:25:1
   |
25 | / static mut FRAMES: [Frame; 2] = [
26 | |     unsafe { MaybeUninit::<Frame>::uninit().assume_init() },
27 | |     unsafe { MaybeUninit::<Frame>::uninit().assume_init() },
28 | | ];
   | |__^ type validation failed: encountered uninitialized raw pointer at [0].iovecs[0].iov_base
   |
   = note: The rules on what exactly is undefined behavior aren't clear, so this check might be overzealous. Please open an issue on the rustc repository if you believe it should not be considered undefined behavior.

is this code equivalent to std::array<Frame, 2> FRAMES;? (I do not know Rust and I'm trying to guess the meaning of the code)

@thedefault. static mut means “mutable global variable”.

I think it might be equivalent?

It's equivalent to the C version, anyway.

Frame FRAMES[2];

MaybeUninit::<Frame>::uninit().assume_init() - sounds like rust wants to tell you about its spiritual journey. first it was asking philosophical questions: "to init or not to init?". after framing the question the right way, it decided that uninit() is the answer, but then had a change of heart and now just assumes init() :)

@ngn I was also doing it wrong, by the way.

In case that wasn't already obvious from my code. :-p

@wizzwizz4 I still want to see a SO question with your coding woes :)

@Anush I don't have any; I'm just that good. :-p

Though, on a scale of one to ten, how bad is this prototype:

pub extern "C" fn main(stack: *const u8) -> !

where stack is a pointer to the function's own stack.

@wizzwizz4 :)

I have no idea!

@Anush How about:

#[inline(never)]  // for correctness

/me sees extern "c", runs away screaming

c++ scares me and its probably for a good reason based on this

@Anush I have a coding woe now (which I think I can fix):

error: invalid register `rsp`: the stack pointer cannot be used as an operand for inline asm
   --> src/main.rs:114:9
    |
114 |         out("rsp") stack_pointer
    |         ^^^^^^^^^^^^^^^^^^^^^^^^

@ReedsShorts c++ scares everyone, it's a mess and everyone secretly knows that

ok at least its not an irrational fear

@ASCII-only why did this get starred its 3am i gave up wording it nicely i don't even know if it's in english anymore

@ASCII-only People like being mean to languages :P

@cairdcoinheringaahing Only PHP, Java, C++, C#, JavaScript, VBScript and Go.

@ReedsShorts do you think there is any advantage in copying the c++ solution into python?

@wizzwizz4 c# wat

@wizzwizz4 Any whatever language you're currently using that isn't doing what you want :P

how dare you

you mean python which is infamous for being slow asf

Sorry, how long does C# take to call main again?

lua and matlab for being 1-indexed. apl, j, k & friends for being "unreadable"

C# is awful. It's just a longer version of C

ngl i cant tell what is going on in the c++ solution

haskell and the MLs, and prolog and erlang for being non procedural and non oop

Having never coded in either, I'm 100% sure that's accurate

@ReedsShorts Dark magic.

@cairdcoinheringaahing *shorter but ok

@ASCII-only Matlab because it's matlab

yeah probably dark magic

@cairdcoinheringaahing same with R and PHP

@ASCII-only the expression slow af always makes me wonder what personal experience inspired it :)

All I'm reading here is that no one dislikes golfing languages :P

@ASCII-only len("C") == 1, len("C#") == 2… Sorry, but the REPL doesn't lie.

either written by non langdevs, or never intended to be a language in the first place (PHP)

@wizzwizz4 get that python outta my face

@cairdcoinheringaahing by the way Entity["Comet", "Comet1PHalley"]["PeriapsisTime"] exists

@cairdcoinheringaahing except for charcoal which isn't golfy enough and also buggy and slow

currently trying to do the prime generating in FALSE and i have to write by own xor

@ASCII-only imgflip.com/i/4sbw4a

wizzwizz4@myLaptop ~/D/~/p/q216902> target/release/q216902 0123456789ABC
0123456789ABC^C⏎
wizzwizz4@myLaptop ~/D/~/p/q216902> target/debug/q216902 0123456789ABC
fish: “target/debug/q216902 0123456789…” terminated by signal SIGSEGV (Address boundary error)

wth is imgflip

@ASCII-only It's an image hosting site.

@cairdcoinheringaahing related

@cairdcoinheringaahing so i clicked the link with my starred messages why the heck did people star those

tnb is weird

@fomin what string are you using for testing the submissions?

@ReedsShorts it's a secret until the bounty is over :) The question explains it is 5 strings of length between 10 and 16

@ReedsShorts did you speed it up just now?

nah so far ovs' optimization is the fastest

if i could understand what the c++ solution does to remove dupes i would implement that

I forgot what it's called when you have two functions f(x) and g(x) and you make a new function f(g(x)), does anyone know?

oh thats composite functions

Oh, thanks!

np

dude for some reason python is so damn slow for the strings

It's a seriously slow language . There is an array data type which people don't talk about much docs.python.org/3/library/array.html

Might that be faster?

@ReedsShorts the author of the c++ answer was here recently. But part of it is just recognising that insert followed by substituting is the same as substituting followed by insert so you don't need to do the same thing twice

Hmm.. waymoot.org/home/python_string

@ReedsShorts Can you use lists instead of strings?

because you have to convert from string to list and list to string

question about C: is there a way to write a typedef for a function that accepts a pointer to the same function type?

typedef .. T ..; //what do i type here?
void f(T*g){..}
int main(){T*g=f;g(g);}

@ngn that'd make a recursive type, which I doubt C allows (even C++ doesn't really, though that's for templates, not functions).

@dzaima it's allowed in struct-s. you can declare one of them just as struct T; and complete the declaration after the other struct. but for some reason this doesn't work for typedef-s.

@ngn that's a completely different sort of thing though. Infinitely recursive types are much more awful than a struct containing a pointer of its own type

@ReedsShorts I clearly misunderstood method 6. Isn't it the fastest?

@ngn you can do things like this cs.princeton.edu/courses/archive/spr96/cs217/precepts/….

@Anush that's for structs, not function types

@ngn how are the automata?

@dzaima yes. Good point

@Anush slower than bruteforce, unfortunately

Hmm... Any idea why?

@dzaima (i.e. assuming predeclaring typedefs worked, it'd be quite non-trivial to make this rightly understand that B* and T* are, in fact, the exact same type)

It feels like it sounds be fast

@Anush edit distance 2 is too short

@ngn what's it like for edit distance 3?

@Anush that's not what the challenge asks for. i haven't tried.

but i expect traversing the automaton would be better, there would be no garbage in the output

@ngn never be limited to the challenge in front of you :)

@ngn by garbage do you mean duplicates?

@Anush yes, or empty lines

Got you

How do you actually iterate over the words recognised by a DFA?

Is it just depth first search?

@Anush yes, like dfs, but of course visiting the nodes multiple times

> This answer was deleted via review 12 months ago by pppery, Wheat Wizard♦, ovs, Stephen, Jonathan Frech, Lyxal.

Jeez, how many people?

@NewMainPosts I'm very tempted to hammer this closed for now because the wikipedia article, images, and description all do not fit the sample I/O (and there's only one case) which leads me to believe many answers with contradictory behavior will appear, and half of them will need to be deleted when this is clarified.

but since I have to go for dinner soon and won't be back for a while I'm not sure I want to close it if I can't reopen it when this is fixed, since it's a pretty minor fix and the rest of the problem is fine.

eh. i'll be back soon enough and i might be able to reopen it on my phone even sooner anyway

@cairdcoinheringaahing Oh, I remember the infinite review bug.

Didn't know it did that, though.

What's our consensus on answering questions you've VTCed?

I'd gotten the impression that it was unrecommended/not well received

@NewMainPosts That was closed 10 minutes ago, and att just answered it :/

@RedwolfPrograms I've usually seen that as well for unclear/no winning criteria, but I'm not sure about dupes

@cairdcoinheringaahing Apparently you can finish answering if you begin before the question is closed.

@Adám You can answer regardless, iirc, though I've been told by a CM not to.

Apparently the limitations of the web client aren't just suggestions.