Implement a memchr wrapper: searchByteArray

Authored by andrewthad on Mar 5 2018, 8:53 PM.



Implement searchByteArray. Under the hood, this is just memchr. It
has to tweak some of the arguments to make it appropriate for use
with haskell's byte arrays. Instead of taking a pointer as an
argument, it takes a byte array plus an offset. Instead of
returning a pointer, it returns an index into the array.

Test Plan

A test case has been added to the test suite. At present, this
test is failing. I still need to convert the pointer that
memchr returns into an index.

andrewthad created this revision.Mar 5 2018, 8:53 PM
alexbiehl accepted this revision.Mar 6 2018, 1:43 AM
alexbiehl added a subscriber: alexbiehl.

Thanks @andrewthad! Generally this looks good to me.


I think foobar is missing from test above.

This revision is now accepted and ready to land.Mar 6 2018, 1:43 AM
alexbiehl added inline comments.Mar 6 2018, 1:53 AM

I assume we need something like

emitAssign (CmmLocal res) (CmmMachOp (MO_Sub (wordWidth dflags)) [CmmReg (CmmLocal res), CmmReg (CmmLocal ba_p)])

as well.

alexbiehl requested changes to this revision.Mar 6 2018, 2:01 AM
This revision now requires changes to proceed.Mar 6 2018, 2:01 AM
andrewthad updated this revision to Diff 15664.Mar 6 2018, 6:22 AM
  • nearly correct implementation
andrewthad added inline comments.Mar 6 2018, 6:24 AM

Thanks. I've made this change, and it's now almost correct. When memchr signals that the character was not found by returning NULL, I still have to clean that up somehow (turn the 0 into -1 instead of performing the subtraction).

bgamari added inline comments.Mar 25 2018, 10:52 AM

Any progress on this?

andrewthad added inline comments.Mar 25 2018, 1:18 PM

I feel a little stuck on finding a satisfactory solution to cleaning up the result. Here's what I mean. If we check for NULL and turn that into -1 instead of performing the subtraction, the very next thing that's always going to happen is that the user is going to case on that number and take a different code path if it's -1. I don't like that this means that we always have two conditionals after calling this function (the first to clean up the result and the second to branch depending on that cleaned up result). It would be neat if there were a way to clean up the result without branching. Maybe this doesn't actually matter though. Maybe the Cmm compiler sees the double conditional and cleans it up. Let me know if I'm obsessing over an optimization detail that won't matter.

dfeuer added a subscriber: dfeuer.Mar 25 2018, 10:40 PM

Would it be worth copying the assembly implementation of memchr from gcc or wherever for X86? And


I haven't dug into the code generation (I really don't know much about that), but another return convention to consider is (# (# #) | Int# #), which seems a lot clearer. Of course, that's also bad if it's not optimized away, but since unboxed sum performance is likely to get continual attention, perhaps it's okay to bet on it getting good if it isn't yet.

andrewthad added inline comments.Mar 26 2018, 8:43 AM

An unboxed sum is certainly the most correct option. There are two reasons I didn't do it. One is that it makes the returned value push two words on to the stack instead of one (but I agree that it's conceivable that this could eventually be optimized away by some part of the compilation process if you case on the result immediately afterwards). The other reason is that I simply couldn't figure out how to do this. There are no existing primops that return an unboxed sum, and it would be helpful to have some code to borrow from as a starting point.

Whoops, I found this comment unsubmitted. @andrewthad, what is the status of this?


I think the current approach is fine; in general I would err on the side of keeping the compiler implementation simple but exposing slightly unsafe primops. User libraries are in a much better position to expose safer interface on top the primop.

I'm going to migrate this over to gitlab. Feel free to close this.

bgamari abandoned this revision.Jan 21 2019, 4:40 PM