expose more primitive operations

[BurntSushi]

As I understand it, the public API currently requires that haystacks be &str and that all needles be ASCII. Might you consider exposing a way to run a search on a &[u8]? And possibly also exposing a way to use arbitrary bytes instead of limiting it to ASCII? (I feel less strongly about the latter point than the former point.)

The specific reason why I'd want this is for use in regex. In particular, the internal matching engines can work on either &str or &[u8], so the prefix literal scanning operates on &[u8] so that it can be used with any of the matching engines. Since all inputs originate with &str (currently), I could unsafely transmute to &[u8] before calling out to jetscii, but I don't think that assumption will always hold in the future and the use of unsafe there seems a little unfortunate.

Other ideas? Thoughts?

[shepmaster]

All of this absolutely makes sense. I actually thought there was an issue for this already, as I'm sure someone else wanted it.

run a search on a &[u8]
a way to use arbitrary bytes instead of limiting it to ASCII

Yeah, I'd probably just set up parallel structures that allow you to do whatever you want with bytes. This would allow folk to use it for binary files where you need to find 255 or somesuch.

For my own education, will you actually be searching for non-ASCII characters? If so, are you just going to search for the first byte of a multiple-byte UTF8 character and then do a sanity check to make sure it was the right one?

[BurntSushi]

@shepmaster regex today does indeed search on bytes, which may be any value in 0-255. The invariants are little more complex than I'd like, but:

1. For the DFA, it matches on raw bytes. UTF-8 decoding is handled implicitly in the compiled program. Since we guarantee (by construction) that the automata can only enter a match state via valid UTF-8, we can do whatever kind of prefix scanning we like---even if it's only part of a single encoded codepoint.
2. For the NFAs, they generally do UTF-8 decoding explicitly since the automata is itself defined in terms of codepoints. (Yup, this means we have two distinct flavors of automata in regex.) When prefix literals are extract from such a program, then the literals are themselves just sequences of codepoints. When we do the actual prefix scanning, if the prefix starts with a non-ASCII codepoint, then it will just pass the first byte to memchr (for example). The matching engine then picks up at the beginning of the literal match, so it never needs to deal with partial decoding or any of that.

With that said...

1. Using memchr on a non-ASCII byte probably isn't wise for performance reasons, and would probably be better to run memchr on, say, the ending byte of a UTF-8 encoding of a single codepoint. The performance picture isn't exactly clear here though.
2. In the future, I would like for Regex to be capable of matching on &[u8], which may contain arbitrary bytes. Today, search text must be valid UTF-8.

Hope that makes sense. Happy to answer more questions!

[shepmaster]

@BurntSushi what kind of API would you like to see? Strings are nice in that they have the Matcher API to bolt into. Byte slices don't seem to have the same thing. There's a bit of setup involved, so there probably wants to be a struct to hold it. My natural inclination is to have something like

let needle = some_macro_name!(needle_byte_1, needle_byte_2, ...);
needle.position(haystack);

But it would probably feel more natural to have haystack.position(needle) which would involve a trait. I'm pretty flexible here, so as an interested API consumer, I think your voice gets a lot of weight! 🌴

[BurntSushi]

@shepmaster Hmm. The absolute simplest API I can think of is: fn pcmpestri(needles: &[u8], haystack: &[u8]) -> Option<usize> (excuse me if pcmpestri is not the appropriate name here). It could panic if needles.len() > 16.

I suspect what you're going to say is that this adds some kind of overhead to every search since the bytes in needles need to be packed into something before being passed to asm!. If that's true, then perhaps:

struct PcmpSearcher {
    // some packed representation?
}

impl PcmpSearcher {
    // Create a new PcmpNeedles with the bytes given.
    // This panics if needles.len() > 16.
    // Duplicate bytes are ignored. (Seems suspicious.)
    fn new(needles: &[u8]) -> Self { ... }
    fn position(&self, haystack: &[u8]) -> Option<usize> { ... }
}

(Naming isn't my specialty. :P)

You could even impl FromIterator so that let pcmp: PcmpSearcher = vec![b'a', b'b', b'c'].into_iter().collect() works, but that might be too much fluff. :-)

Other thoughts:

1. I could live with a trait, but there's really nothing in this space for &[u8], so my natural inclination is to not add any.
2. I think a macro would be regrettable.

[BurntSushi]

@shepmaster Thanks for working with me on this btw. I actually think this might help regex catch up to PCRE on a few benchmarks (because they are precisely the benchmarks with a small number of prefix bytes). At least on Rust nightly, anyway. :-)

[shepmaster]

I think a macro would be regrettable.

The macro is to allow for fallback cases where the intrinsic operations aren't available. Technically, I could make a few small changes and release Jetscii right now and it would work on stable Rust. It just isn't worth it because the fallback would be the only supported case!

Right now, when you call something like:

part_number.split(ascii_chars!('-', ':')).collect();

That macro expands into the packed structures needed for the intrinsic as well as an optimized closure that checks for those two bytes "manually" (part_number.as_bytes().position(|b| b == '-' || b == ':')). Conditional compilation means only one path is actually used.

This all corresponds to AsciiChars and AsciiCharsWithFallback.

If you compile with the right features (which the docs don't), then there are methods on AsciiChars like find, which returns the byte index.

It's possible that you'd prefer to have your own fallback code for when the intrinsics aren't available. If so, then you'd be able to use the raw-bytes equivalent of find (which I agree should be called position in the context of bytes).

---

I did think about the one-shot function, and it's something I'd be open to if enough people wanted it, but I look at it as a bit of antipattern - you probably don't want to call it in a tight loop, much like Regex::new.

The FromIterator implementation is indeed cute, and I'll have to give some thought to that. 😸

[shepmaster]

Thanks for working with me on this btw.

Absolutely! Having people use the library is the only way it will get better! And the faster Rust is, the more likely I am to get paid to write it for a living! 😇

[BurntSushi]

Hmm, right, so then I definitely agree that the one-shot case should just be completely thrown out the window. Encouraging folks to write slow code is bad (and is one reason why, e.g., I want to remove the free function is_match from regex when it hits 1.0).

With that said... you're right about the fallback. I definitely want to be able to control, up front, which type of prefix searching is used. Sometimes it's just memchr, sometimes it's Boyer Moore and other times it's Aho-Corasick (and of course, the latter two make use of memchr internally, and hopefully jetscii too!). If for some reason the prefix isn't amenable to pcmpstri, then I want to choose a different strategy at compile time.

I think the fallback code is nice from a usability perspective, but I do also believe there should be a way to execute pcmpstri with as few assumptions as possible. I think that's what I'd like most.

Now, if for some reason it's impossible to know whether a fallback is needed up front, then that could be a problem! (I feel like there shouldn't be, but my understanding of the pcmpstri instruction is extremely limited.)

With all that said, if you feel strongly about tying it to a fallback in the public API, then I can cope and write my own fallback routine. :-) (For example, I'd use memchr2 in the memchr crate before the naive iterator approach if there are two bytes.)

[shepmaster]

I don't think I am doing a great job explaining, but hopefully code will help. Grab the bytes branch. You should be able to use jetscii::bytes::Bytes:

extern crate jetscii;

use jetscii::bytes::Bytes;

fn main() {
    let words = include_bytes!("/tmp/words.gz");
    let mut needle = Bytes::new();
    needle.push(0x80);
    println!("{:?}", needle.position(words));
}

Make sure you compile Jetscii with features=["unstable"] to enable everything (and a nightly, of course).

The big thing is that Bytes::position does not exist unless you

1. Have the feature enabled
2. Are on x86_64

The fallback code I'm talking about makes it so a consumer of the library doesn't need to know about those concerns. You want to care about that, and this is the current way I expose it.

[BurntSushi]

@shepmaster Code is good, thanks for that. And it has made me realize that I had a major brain fart. For whatever reason (I blame lack of sleep), I was thinking that the fallback was used when a caller added more than 16 bytes to the needle, but now of course I realize that's silly. I forgot about the pcmp instructions not being supported everywhere!

So with that said... Yes, I would use with_fallback and do my special memchr stuff in there. :-) Sorry for the confusion! Up to you whether you should still have position on the Bytes type.

[shepmaster]

I would use with_fallback and do my special memchr stuff in there

Hmm. That makes sense, but could be a bit tricky. Right now, the fallback takes a Fn(u8) -> bool which is usually provided with a closure like |b| b == b'A' || b == b'Z'. It's really impressive how well the compiler optimizes and inlines those!

In fact, a lot of my existing usage has centered around a set of characters fixed at compile time. For example, XML parsing can benefit from looking for the first of ['&', '<', '>']. You can see the benchmarks to see that an inlined closure is about 1 GB/s faster than a slice!

In your case, you'd rather a fallback that operates more like Fn(&[u8]) -> Option<usize>, basically a complete substitute implementation.

I can certainly add something like that, but it starts to feel a bit circular. What would you actually be using for your fallback? I'd assume something like memchr. If that's the case, then perhaps that's what Jetscii should actually be using under the hood any way.

[BurntSushi]

What would you actually be using for your fallback?

Yes, absolutely. :-)

The memchr functions are here: http://burntsushi.net/rustdoc/memchr/ Note the existence of memchr2 and memchr3, which I cobbled together specifically in cases where something like jetscii can't be used. They should be faster than the naive |b| b == b'A' || b == b'Z'.

@huonw - I wonder if you might have any special knowledge in this space, since I know you've been working on simd stuff. (I've looked at it, but can't quite grok how to use it for substring/byte matching!)

[shepmaster]

One thing I notice is that your performance numbers for memchr blow Jetscii out of the water:

which	speed
Iterator::position	1893 MB/s
memchr	49504 MB/s
Jetscii	5719 MB/s

I'm not even sure why you'd want to switch!

[BurntSushi]

@shepmaster Hehe, well that's memchr, which only works on a single needle and is defined inside libc which is probably doing all sorts of cool things. It would be better to compare jetscii with memchr2 and memchr3, which I wrote based on memchr's fallback code written by @bluss. Even then, memchr2 and memchr3 only support 2 and 3 needles respectively, whereas jetscii will go up to 16.

To be clear, when there's a single leading byte, I won't use jetscii---I'll just use memchr. But if there's more than that.... :-)

[BurntSushi]

Here are the latest benchmarks in memchr from Travis: https://travis-ci.org/BurntSushi/rust-memchr/jobs/109233136#L251-L258 --- I'm not sure if those numbers are directly comparable to what you have in jetscii's README (but you could run the benchmarks on the same machine easily enough).