9 ms·
Writing a JPEG Decoder in Rust – Part 2: Implementation I
- 0x0 10y agoI don't know rust, but what happens if you get a 0xff as the last byte here, wouldn't i+1 go out of array bounds? while i < vec.len() { encoded_data.push(vec[i]); if vec[i] == 0xff && vec[i + 1] == 0x00 { // Skip the 0x00 part here.
- deleted 10y ago[deleted]
- ekidd 10y agoIIRC, Rust will panic and halt your program. This is one of a handful of errors that Rust can't catch at compile time, and so it inserts run-time checks. The syntax "vec[i+1]" means "I expect this index to be in bounds, and if it's not, my program is so hopelessly broken it should be shut down immediately." If you're really confident in your code and you need to wring out the last bit of performance, you could also use: unsafe { vec.get_unchecked(i+1) } ...but in this case, your code would produce undefined behavior. If you want to detect this case and recover from it, you could also write: if let Some(value) = vec.get(i+1) { // Use value. } else { // Fail with an error. } ...or you could immediately exit the current routine with an error if no value is available: let value = try!(vec.get(i+1).ok_or(make_an_error())); If you're writing a lot of parser code, your best bet might be to define a custom macro named that looks something like "try_get!(vec, i+1)" wrapping the final example above.
- steveklabnik 10y ago> and you need to wring out the last bit of performance, ... and if you've already demonstrated that LLVM hasn't removed the bounds checks itself already.
- grayrest 10y agoSince Rust people are reading this. I find myself wanting to walk an iterator pairwise regularly for stuff like this and I'm using: for (cur, next) in (& vec).iter().zip(vec.iter().skip(1)) { encoded_data.push(cur); if cur == 0xff && next == 0x00 { // ... } } Is there a better way to write this? What I'd really like is the equivalent to Clojure's partition[1]. I know that the stdlib has windows `(partition n (dec n) seq)` and chunks `(partition n n seq)` implemented on slices but I usually want this on iterators for the lookahead-like behavior shown here. [1] https://clojuredocs.org/clojure.core/partition https://clojuredocs.org/clojure.core/partition
- steveklabnik 10y agoI'm not 100% sure, but https://crates.io/crates/itertools https://crates.io/crates/itertools might have what you're looking for.
- elktea 10y agoI think http://bluss.github.io/rust-itertools/doc/itertools/struct.Zip.html http://bluss.github.io/rust-itertools/doc/itertools/struct.Z... would fit their use case?
- dbaupp 10y agoThe `.windows(usize)` function almost does this, but it uses a runtime width and so has to yield slices rather than tuples.
- doomrobo 10y agoIf you can afford the allocation at every iteration, the iterslide crate might work for you. https://github.com/slapresta/rust-iterslide https://github.com/slapresta/rust-iterslide
- martinhath 10y agoOoops :( One of many minor bugs, I suppose.
- bluejekyll 10y agothis is a really elegant way to take parallel arrays and put them into a table: let codes: Vec<HuffmanCode> = data_table.iter() .zip(code_lengths.iter()) .zip(code_table.iter()) .map(|((&value, &length), &code)| { HuffmanCode { length: length, code: code, value: value, } }) .collect(); Nice!
- masklinn 10y agoYeah though there's something a bit sad to the lack of variable-arity zip/map as you'd find in dynamically typed languages e.g. in Clojure: (mapv HuffmanCode. code_lengths code_table data_table) I don't know if even dependent types would allow for that, given the (variable number of) arguments are all different types.
- lmm 10y agoIt's straightforward with dependent types, unless the language treats multiple arguments (or functions of multiple arguments) specially. In my Scala example in the sibling thread the ().zipped is sort-of-language-level, but one could easily implement the same thing using a HList instead of a tuple; turning the function into a function that accepts a HList requires language-level support or a (standardized) macro but it wouldn't in a Haskell-like language where a function of multiple arguments is curried by default.
- lmm 10y agoIt seems like a lot of work? In scala this would just be: val codes = (data_table, code_lengths, code_table).zipped map HuffmanCode
- daconvergence 10y agoRust code looks very similar to ES6 or Typescript. The great CS language convergence has begun!
- tdb7893 10y agoAs far as I know languages have broken down into families that look pretty similar to each other for a long time.
- lmm 10y agoI think there is some convergence. E.g. there seems to be broad consensus that at least some level of standardisation of type information is valuable (see Python adding/improving type annotation syntax), and at the same time that having to explicitly specify the type of absolutely everything probably isn't worth it.
- quotemstr 10y agoYes: now we all forget how to correctly manage memory. Rust: where resources are unlimited and aborting when you run out of them is okay
- pcwalton 10y ago"Rust: where resources are unlimited and aborting when you run out of them is okay" I'd change "Rust" to "safe programming" here, but OK. There have been lots of fun security vulnerabilities coming from programs trying to handle OOM gracefully. e.g. SpiderMonkey: https://bugzilla.mozilla.org/show_bug.cgi?id=982957 https://bugzilla.mozilla.org/show_bug.cgi?id=982957, https://bugzilla.mozilla.org/show_bug.cgi?id=730415 https://bugzilla.mozilla.org/show_bug.cgi?id=730415
- Manishearth 10y agoRust has provided ways to not abort on oom for a while now.
- 10y ago
- juliangoldsmith 10y agoOriginal thread: https://news.ycombinator.com/item?id=12319557 https://news.ycombinator.com/item?id=12319557
- martinhath 10y agoOh well - not getting karma on HN isn't the worst thing that could've happend :)
- Artlav 10y agoI feel like i'm missing something. In the "Why" section he claims that Rust is a performant language with a low-level feel. In this part, he claims that decoding a tiny JPG image took 2 seconds with his code. How is that "performant" by any definition?
- pcwalton 10y agoMany language implementations generate code with good performance. That does not mean that all programs written in those languages will exhibit good performance.
- ape4 10y agoMake it work, then optimize.
- dbaupp 10y agoA language allowing high performance code doesn't mean it automatically guarantees high performance code. The latter is essentially impossible. One common pitfall is not turning the optimiser on (with --release for cargo) i.e. benchmarking a debug build rather than a release one, and from a quick glance this code looks like it may be doing a system call to read each and every byte of the file due to the use of .bytes() on an unbuffered file, whereas it would be better to use, say, read_to_end to read many bytes of the file at once.
- balducien 10y agoSomebody on reddit found the bottleneck: https://www.reddit.com/r/rust/comments/4yinbt/writing_a_jpeg_decoder_in_rust_part_2/d6obz7r?context=2 https://www.reddit.com/r/rust/comments/4yinbt/writing_a_jpeg... After fixing it, it apparently runs in 100 ms.
- martinhath 10y agoIt's worth mentioning, those numbers are for my test program which only read a single file, using my and his implementations. In addition, the file read was 20MB. lena.jpeg is 90K.
- 10y ago
- pslam 10y agoIf you scan through the source (on github), the most notable thing is the lack of the "unsafe" keyword. I've seen too many people basically transliterate from C to Rust, along with all the unsafe operations. This one is pretty much unoptimized, but still seems to be performant enough, and doesn't do anything "unsafe". That's not to say you could just throw this into the back-end of a public-facing website. It's still going to panic (abort) if someone unexpected happens, and it's still going to chew indeterminate amounts of CPU, memory or storage unless sandboxed (maybe even just ulimit). And there's still the danger one of the Rust standard library functions has a flaw in it. But this is the kind of starting point you wouldn't get with the plain C equivalent.
- technion 10y agoGiven the history of vulnerabilities in tools like ImageMagick, that panic might still be a better position than an exploitable memory bug.
- conradev 10y agoIf you run it in a spawned thread, the thread will actually just unwind and disappear if it panics (by default). But to detect panics, you can use `afl.rs` to fuzz a parser: https://github.com/frewsxcv/afl.rs#user-content-trophy-case https://github.com/frewsxcv/afl.rs#user-content-trophy-case
- EugeneOZ 10y agoGiven the fact you can avoid panic and exit safely, all panicking is just laziness ;)
- jakub_h 10y agoIsn't it the case that at least some unsafe features in C actually prevent compiler optimizations? Being safe should not necessarily mean being slower. Sometimes restrictions are enablers for better compilers.
- namelezz 10y ago[0] an old decoding speeds survey of existing JPEG decoders(2010). [0] - http://www.briancbecker.com/blog/2010/analysis-of-jpeg-decoding-speeds/ http://www.briancbecker.com/blog/2010/analysis-of-jpeg-decod...