[racket-users] Performance of the Racket reader
I've written a command-line tool in Racket to analyze the files produced by a tool that traces accesses to persistent memory by an application. The traces are large: about 5 million records per second of application run time. While developing the tool in Racket was a pleasant, productive, and educational experience, the execution time of the tool has become an issue. I have some ideas of ways to improve the analysis logic, but I think the trace reader may perform so slowly that the result would still be unusable. The trace records are in a binary format. I have a C++ tool that reads the binary trace file and outputs them in a simple sxml-ish textual form to stdout. I pipe this into my Racket tool, that then uses the standard Racket reader to parse the s-expressions arriving on its stdin. I excised all the analysis code from from my tool and just benchmarked the performance of the trace reader. It can only read about 62,000 s-expressions per second on a 2.4 GHz Xeon E5-2630 v3 (Haswell) system. I'm using Racket v6.7. I've provided the trace reader code below. Have I botched something that would make it perform so slowly? I'd rather not have to recode it in C++. The input to the tool looks like this: (pmem_flush (threadId 140339047277632) (startTime 923983542377819) (elapsedTime 160) (result 0) (addr 0x7fa239055954) (length 1)) (pmem_drain (threadId 140339047277632) (startTime 923983542378153) (elapsedTime 83) (result 0)) The trace record reader code: #! /usr/bin/env racket #lang racket (require racket/cmdline) (require racket/runtime-path) ; ; apply trace parser to a stream of trace records ; ; lazy stream of all datums from the input port (define (make-trace-stream in) (let ([datum (read in)]) (if (not (eof-object? datum)) (stream-cons datum (make-trace-stream in)) empty-stream))) ; apply a set of trace-stat% classes to the stream of trace s-expressions ; return a trace-state struct containing the statistics of the trace (define (map-trace stat%-set in-port) (for/fold ([sexp-count 0]) ([trace-record (in-stream (make-trace-stream in-port))]) (+ sexp-count 1))) ; apply a null set of trace-stat% classes (define (accumulate-default-trace-stats in-port) (map-trace null in-port)) (define (print-accumulated-default-trace-stats in-port) (printf "s-expression count: ~a\n" (accumulate-default-trace-stats in-port))) ;;- ;; command-line parsing (module+ main (print-accumulated-default-trace-stats (command-line #:args args (if (null? args) (current-input-port) (open-input-file (first args)) Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Performance of the Racket reader
Hi Mathias, Thanks for taking a look. > On May 31, 2017, at 4:13 PM, Matthias Felleisen wrote: > > > Can you explain why you create a lazy stream instead of a plain list? The current size of a short binary trace file is about 10 GB, and I want to scale to traces many hundreds of megabytes in size. The expanded s-expression form is about 10 times larger, so keeping the whole list in memory could require up to many terabytes of memory. Aside from just handling large traces, I also parallelize the problem by running analysis processes on different trace files concurrently. So the amount of memory required for the parallel computation would be about 32 times the memory needed for a single trace analysis process. So, I don't want to try to fit all the records in memory at once. I thought that the lazy stream would accomplish this --- am I wrong? Is there a better way than lazy streams to write on-line algorithms, i.e. algorithms that process a stream of input data without first reading it all into memory? > Your code is strict in the stream so the extra memory for a stream is > substantial and probably wasted. Perhaps the below is simplified and you > really need only portions of the lazy stream. — Matthias Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Performance of the Racket reader
Hi Jon, > On May 31, 2017, at 6:14 PM, Jon Zeppieri wrote: > > On Wed, May 31, 2017 at 5:54 PM, Steve Byan's Lists > wrote: >> So, I don't want to try to fit all the records in memory at once. I thought >> that the lazy stream would accomplish this --- am I wrong? > > You're right, but using a lazy stream will still consume more than > just using `read` within the loop that actually processes the data. > So, for example: > > (define (map-trace stat%-set in-port) > (for/fold ([sexp-count 0]) >([trace-record (in-port read in)]) >(+ sexp-count 1))) > > (I didn't try this, but I think it's right.) > > This way, you don't build up a list or a lazy stream; you just process > each datum as it's read. Thanks, I don't recall why I didn't think of this alternative. I guess I was hung up on streams, or else not thinking of s-expressions as lists :-( Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Performance of the Racket reader
> On May 31, 2017, at 6:32 PM, Matthias Felleisen wrote: > >> >> On May 31, 2017, at 6:14 PM, Jon Zeppieri wrote: >> >> >> This way, you don't build up a list or a lazy stream; you just process >> each datum as it's read. > > > Yes, that’s what I would have proposed next. Just fuse the two functions and > rely on port reading to do the ‘right thing’. Thanks, I'll try that. > I understand that this violates John Hughe’s ‘modularity’ argument in support > of lazy programming but in return, you will need much less space and get a > faster reader. That's just what I need. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Performance of the Racket reader
Hi Neil, Thanks for the comments. > On May 31, 2017, at 8:21 PM, Neil Van Dyke wrote: > > In addition to what others have mentioned, at this scale, you might get > significant gains by adjusting your s-expression language. > > For example, instead of this: > > (pmem_flush > (threadId 140339047277632) > (startTime 923983542377819) > (elapsedTime 160) > (result 0) > (addr 0x7fa239055954) > (length 1)) > (pmem_drain > (threadId 140339047277632) > (startTime 923983542378153) > (elapsedTime 83) > (result 0)) > > You could reduce consing by making each name-value pair be a single Racket > pair, rather than a proper list: > > (pmem_flush > (threadId . 140339047277632) > (startTime . 923983542377819) > (elapsedTime . 160) > (result . 0) > (addr . 0x7fa239055954) > (length . 1)) > (pmem_drain > (threadId . 140339047277632) > (startTime . 923983542378153) > (elapsedTime . 83) > (result . 0)) > > The proper list is what you'd want for a human language, and in most > applications the extra cost would be negligible, but you might have an > application in which it matters. I did consider using an association list representation for the attributes, but I'm depending on s-expression pattern matching for parsing the records. It's wonderfully convenient for this. I'm under the impression that `match` requires proper lists as input. While pattern-matching was wonderful for putting together the analysis tool quickly, I don't know how much of a bottleneck it is in the overall performance, so I may have to abandon it. > > Your file size grows by an extra 2 bytes per pair, though, and this will also > have a small additional I/O handling cost. > > Another thing you could do is, if one of your message types (like > `pmem_flush`) always/often has the same attribute names, is to make the > attributes "positional": > > #(pmem_flush 140339047277632 923983542377819 160 0 0x7fa239055954 1) > #(pmem_drain 140339047277632 923983542378153 83 0) > > If what's currently `pmem_flush` usually has the same attribute names, but > occasionally has an extra one, and you don't want to always be filling in > `#f`, maybe you want a `pmem_flush` with the positional attributes, and > `pmem_flush_extra` that has an extra positional attribute. The records are fixed-format, except that the trace record for system calls that take an I/O vector as an argument has a variable length list representing the struct iov array. > > If the possible variations of `pmem_flush` are more complicated, maybe > `pmem_flush` with positional, in the usual case; and `pmem_flush_named` with > named attributes or a hybrid of positional and named, in the complicated > cases. Then you have the various development costs of two ways of doing one > thing, but sometimes that happens in runtime performance optimization. > > I used a Racket vector here, to suggest fast direct access to the attribute > values, but if you used a list, you could destructure it to named > variables/slots with `apply` and `lambda` (or with `apply` and a `struct` > constructor, if that made sense). I found it essential to use named variables for the attributes, for my own sanity while writing the code. I'd appreciate a short example of what you mean by using `apply` and `lambda` to destructure the list. > > If you still find that this data interchange I/O is expensive, you can always > second-guess whether the reader is a win (over, say, a Unix-y > spaces-and-linefeeds format, or a binary format). But usually the reader is > fast. If I have to give up too much in programming convenience, I may as well just recode it in C++. Racket would still have been valuable in enabling me to quickly evolve the design. > BTW, some Algorithms 101 text once told me that constants don't matter, only > complexity, but that noble lie was just confusing. :) Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Performance of the Racket reader
> On Jun 1, 2017, at 12:25 AM, Neil Van Dyke wrote: > > Steve Byan's Lists wrote on 05/31/2017 10:05 PM: >> I'd appreciate a short example of what you mean by using `apply` and >> `lambda` to destructure the list. > > I'll babble more than you want here, in case anyone on the list is curious in > general... > > #lang racket/base > > (define (do-something-with-pmem-drain-record thread-id start-time > elapsed-time result) > (log-debug "DRAIN RESULT ~S" result)) > > (define (do-something-with-pmem-flush-record thread-id start-time > elapsed-time result addr length) > (log-debug "FLUSH RESULT ~S" result)) > > (define (do-something-with-record record) > (case (car record) >((pmem_drain) (apply do-something-with-pmem-drain-record > (cdr record))) >((pmem_flush) (apply do-something-with-pmem-flush-record > (cdr record))) >(else (error 'do-something-with-record > "invalid record ~S" > record > > (define example-input > (open-input-string "(pmem_drain 140339047277632 923983542378153 83 0)")) > > (do-something-with-record (read example-input)) > > That's just one way to do it that's rapid to write initially, maintainable, > and (possibly) very efficient at runtime. Thanks, I understand the idea. It looks promising. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Performance of the Racket reader
Hi Jon, > On May 31, 2017, at 6:41 PM, Steve Byan's Lists > wrote: > >> On May 31, 2017, at 6:14 PM, Jon Zeppieri wrote: >> >> So, for example: >> >> (define (map-trace stat%-set in-port) >> (for/fold ([sexp-count 0]) >> ([trace-record (in-port read in)]) >> (+ sexp-count 1))) >> >> (I didn't try this, but I think it's right.) >> >> This way, you don't build up a list or a lazy stream; you just process >> each datum as it's read. > > Thanks, I don't recall why I didn't think of this alternative. I guess I was > hung up on streams, or else not thinking of s-expressions as lists :-( Alas, it's only a 13% reduction in run-time. About 91K records/second as opposed to 80K records/second. (I'm running on a system with turbo-boost enabled today, hence the 80K recs/sec for the stream instead of the 62K I reported yesterday.) I'll make another try using Neil's approach of formatting the trace records as a simple list. Best regards -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Performance of the Racket reader
> On Jun 1, 2017, at 10:52 AM, Steve Byan's Lists > wrote: > > Hi Jon, > >> On May 31, 2017, at 6:41 PM, Steve Byan's Lists >> wrote: >> >>> On May 31, 2017, at 6:14 PM, Jon Zeppieri wrote: >>> >>> >>> This way, you don't build up a list or a lazy stream; you just process >>> each datum as it's read. >> >> Thanks, I don't recall why I didn't think of this alternative. I guess I was >> hung up on streams, or else not thinking of s-expressions as lists :-( > > Alas, it's only a 13% reduction in run-time. About 91K records/second as > opposed to 80K records/second. (I'm running on a system with turbo-boost > enabled today, hence the 80K recs/sec for the stream instead of the 62K I > reported yesterday.) > > I'll make another try using Neil's approach of formatting the trace records > as a simple list. Using a simple list gives a 65% reduction in run-time for just reading in the list with the reader. About 256K records/sec. But it's still one and one-half orders of magnitude slower than sucking in the binary, and I'd have to do a fair amount of revision to the Racket code, as well as revising the C++ code that generates the text form of the trace records. And then I'd have to recode the Racket analysis classes to be imperative to try to speed _them_ up. I might be able to get the Racket performance to an acceptable range, but I need to move on to actually using the tool, and I'm more confident that I'll get usable performance recoding it in C++ than by revising the Racket prototype.Thanks for everyone's help, I've learned a lot. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] class copy constructors
I'm trying to make some simple use of Racket's class and object system, but I'm having trouble using the documentation to figure out how to accomplish something. I want to create both a no-argument default constructor and a copy-constructor. I don't see how to accomplish that. If I declare an initialization variable for the copy constructor, I don't see how to provide a default value for that initialization variable that would be compatible with field initialization expressions that use an "other-object" initialization variable. Further, I would really like to provide different field initialization expressions for the default constructor and the copy-constructor (the copy-constructor would be a recurrence relation and the default constructor would provide the initial conditions). I could use a Smalltalk-like approach with a default field initialization expression and an imperative "copy constructor" that updates the default values using set!, but I'd rather take a more functional approach. Could someone provide an example of how to accomplish this functionally? Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] class copy constructors
Never mind, I got it: (define baz% (class object% (init (foo 0)) (define bar foo) (super-new) (define/public (get-bar) bar) (define/public (copy-baz) (new baz% [foo (+ (get-bar) 2)] > (define a (new baz%)) > (send a get-bar) 0 > (define b (send a copy-baz)) > (send b get-bar) 2 In hind-sight, I don't know why it wasn't obvious to me at the time. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] math/statistics running expected values
Thanks for the excellent statistics library, especially the on-line algorithms for the statistics object. However, I often need to partition a large population into subsets, obtain the statistics of each subset, and obtain the statistics of various unions of the subsets as well as for the entire population. In the past (and in other languages not as fun as Racket) I've done this using Chan's parallel algorithm for the mean and variance and Terriberry's extension of Chan's algorithm for skewness and kurtosis, so that I can keep running statistics on each disjoint subset and later combine them for the various aggregations. I'd like to similarly extend math/statistics to enable the summation of the running statistics. However, I'm not very statistics-savvy and so I'm having trouble following the algorithm in the update-statistics function that handles weighted samples. I also don't have ready access to Pébaÿ's recent papers that extend Terriberry's method to handle weighted samples, and I probably wouldn't understand Pébaÿ's paper anyway :-( So on to my questions: Is the algorithm used in the update-statistics function amenable to being extended to a parallel version? In other words, do the moments in the statistics structure correspond to the first through fourth central moments? Is anyone here familiar with the extensions to the parallel algorithms that handle weighted samples? I'd like to support weighted samples, but I just don't know how to handle them. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] math/statistics running expected values
Hi Jack, > On Jan 27, 2017, at 3:57 PM, Jack Firth wrote: > > I don't have enough stats experience to help with the details of your > problem, but I'd like to suggest adding a separate package that extends > math/statistics. You'll likely have an easier time developing and testing it, > and you won't have to worry about adding extra dependencies to the built in > math library. The internal state that I need to access in the statistics struct for this extension are documented as "hidden fields ... used to compute moments, and their number and meaning may change in future releases". I haven't tested it, but my impression is that the hidden fields are not accessible outside of math/statistics. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] read from stdin, except when run in DrRacket
I'm working on a script that I eventually plan to invoke from the command line. I'd like the script to either take a file name argument or, if no arguments, read from stdin. However, while developing the script in DrRacket, I'd like to not invoke the top-level function, and to instead define an input port on a test file for convenience when exercising the code from the DrRacket REPL. Is there a way for a module to distinguish between running in DrRacket and running from the racket or gracket command? Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] read from stdin, except when run in DrRacket
> On Feb 8, 2017, at 2:02 PM, Ben Greenman wrote: > > One idea: you can put the argument-parsing code in the "main" submodule, then > tell DrRacket not to run the main submodule. [snip] > Then in DrRacket, click "Language -> Choose Language -> Show Details -> > Submodules to Run" and un-check "main". Thank you! That's the ticket. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] read from stdin, except when run in DrRacket
> On Feb 8, 2017, at 2:06 PM, Matthias Felleisen wrote: > > > I thought of giving this answer too, but if this is about testing let me > propose a slightly different approach: Thanks. By "testing" I meant flailing around in the REPL while I a) learn Racket and b) figure out the logic for my program, not exercising unit tests. But your approach is perfect for unit testing. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Functional object-oriented programming
I'm just learning Racket's object system. I feel like I've missed something, as it seems pretty verbose to functionally update objects. The pattern I use when functionally updating object state is to invoke the class constructor with a full set of arguments, some subset of which have updated values. Something like this: #lang racket (require math/statistics) (define foo% (class object% (super-new) (init name) (init (stat empty-statistics)) (field [my-name name] [my-stat stat]) (define/public (update-stat x) (new this% [name my-name] [stat (update-statistics my-stat x)] (define foo-stats (for/fold ([current-foo (new foo% [name "foo-object"])]) ([x (in-list (list 0.1 0.5 0.15 0.4 0.09))]) (send current-foo update-stat x))) When the class has lots of fields, it is pretty verbose to provide all the arguments to the constructor, even for fields that are not being updated. I feel like I'm missing something that would reduce the amount of typing involved. I suspect the "something" is macros, but I'm not there yet in my journey through Racket-land. Is there some pre-fabbed construct that I've overlooked? Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Re: Functional object-oriented programming
Matthias, thanks for the confirmation that macros are the answer. Yes, mutation could be simpler. I'm learning more doing it functionally. Alex, thanks for pointing out struct-copy. I hadn't read that part of the Racket Guide yet. Would it be possible to write a macro that when invoked within a class definition would generate a "new-copy" method that behaves like struct-copy? I would guess that Racket has enough introspection to allow that. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Re: Functional object-oriented programming
> On Feb 8, 2017, at 9:05 PM, Philip McGrath wrote: > Personally, I tend to end up defining helper functions to do functional > update (often with optional keyword arguments to address the > fields-that-stay-the-same issue). Generics in the sense of racket/generic can > be helpful for this if using structs. I may then implement the helper > function using struct-copy, but I can hide away its idiosyncrasies. Thanks for the comments, Phillip. A helper method with keyword arguments might make my code more concise. Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Providing a seed to random number generators (and thence to distributions)
In some tests I'm writing, it would be helpful to have the math-lib random number generator (and distributions built upon it) return a deterministic sequence. I didn't see anything in the documentation, but perhaps I overlooked something. Is there a way to set a seed for a random number generator? Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Providing a seed to random number generators (and thence to distributions)
> On Feb 16, 2017, at 1:33 PM, Matthias Felleisen wrote: > > > > > http://docs.racket-lang.org/reference/generic-numbers.html?q=random%20see#%28def._%28%28quote._~23~25kernel%29._random-seed%29%29 Thank you! Best regards, -Steve -- Steve Byan steveb...@me.com Littleton, MA -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.