And to answer my own question about a reference for this change in behavior, which appears to have been made in Java 7:
http://stackoverflow.com/questions/16123446/java-7-string-substring-complexity Andy On Tue, Jun 11, 2013 at 3:33 PM, Andy Fingerhut <andy.finger...@gmail.com>wrote: > Mark, > > I had not heard about Java changing the substring operation from O(1) to > O(n). Do you have a link to any further info about this change? > > I'm guessing that the implementation is changing from the O(1) "create a > new String object that is a reference to a portion of the original String > object" to O(n) "create a new String object that is a copy of a portion of > the original String object"? > > If so, note that it is undesirable in some cases that the O(1) substring > operation works as it does, because it prevents the longer string from > being GC'ed if it would become garbage, except for the fact that one has > created and keeps substrings of it around. One can explicitly call the > String constructor to copy the substrings if you want to avoid that > behavior, of course, so the O(1) with the O(n) fallback is more flexible in > that it lets the developer aware of this behavior choose between them. > > I haven't done anything but think about it during commute time yet, but I > had been wondering in how many situations it might be useful to have a > string type that was something like Relaxed Radix Binary trees, in that > they can be concatenated and substring'd in O(log n) worst case time, and > yet substrings would only hold onto references of the parts that they > explicitly refer to, and perhaps a little bit more (but not the entire > original string). > > Andy > > > On Tue, Jun 11, 2013 at 3:09 PM, Mark Engelberg > <mark.engelb...@gmail.com>wrote: > >> Honestly I hadn't yet given it any thought. Thanks for the interest in >> having it on Clojurescript. Here are a few issues that come to mind: >> >> 1. To achieve performance, I've spent time coding custom data structures >> that implement various Clojure and Java interfaces. I haven't done much >> with Clojurescript, but my impression is that the ecosystem of protocols is >> completely different, so I imagine that could be a pain to transfer over. >> >> 2. I don't know much about the performance of Javascript/Clojurescript's >> underlying data structures. For example, in Java, the substring operation >> used to be O(1), but recently, much to my dismay, they changed it to O(n). >> That change was annoying, and it means I'm going to have to rework some >> code to deal with that, but at least I heard about it and can take it into >> account. But in Javascript I don't even *know* the performance >> characteristics of its strings and substring operation. What other >> Javascript performance gotchas don't I know about? >> >> 3. I'm assuming that due to the above, it won't be as simple as just >> recompiling the code for Clojurescript. I have no idea what's involved >> with maintaining a code base for the two target languages simultaneously. >> Sounds non-trivial, although maybe it won't seem so intimidating once >> things have settled down and I'm not making quite so many performance >> tweaks and feature enhancements to the code. >> >> In any case, please add your request as a github issue, so I don't forget >> about it. >> >> >> On Tue, Jun 11, 2013 at 8:06 AM, JeremyS <jschoffen....@gmail.com> wrote: >> >>> Hi Puzzler, >>> >>> I was wondering if you planned to port Instaparse to ClojureScript. I >>> know it's asking a lot, but I am one of those who would love >>> to be able to run it in a browser or in node.js... >>> >>> Cheers, >>> >>> Jeremys. >>> >> -- >> -- >> You received this message because you are subscribed to the Google >> Groups "Clojure" group. >> To post to this group, send email to clojure@googlegroups.com >> Note that posts from new members are moderated - please be patient with >> your first post. >> To unsubscribe from this group, send email to >> clojure+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en >> --- >> You received this message because you are subscribed to the Google Groups >> "Clojure" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to clojure+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
