You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucy.apache.org by Nick Wellnhofer <we...@aevum.de> on 2013/08/24 00:33:22 UTC
[lucy-dev] cfish-string branch
Hi Marvin,
I just saw that you started to work on an immutable string class. It's a good idea to get this done before the first Clownfish release. Some implementation details have already been discussed on lucy-dev and I have an unpublished, local branch where I continued to flesh out the design of string iterators.
I see that you made CharBuf inherit from String as a temporary measure. It seems that you have a plan on how to make a gradual transition to immutable strings which would be great. Can you share some details about the separate steps so I could help with some of the work? From what I understand, the process should roughly look like this:
* Move a couple of methods from CharBuf to String.
* Implement string iterators.
* Make CFC convert between Perl and Clownfish strings.
* Implement a "zombie" string class?
* Step-by-step conversion of CharBufs to Strings.
* Make CharBuf a separate class.
Nick
Re: [lucy-dev] cfish-string branch
Posted by Nick Wellnhofer <we...@aevum.de>.
On Sep 13, 2013, at 03:25 , Marvin Humphrey <ma...@rectangular.com> wrote:
> The root problem with TextTermStepper is that Lexicon was conceived as a
> wrapper around a mutable object -- the "term" -- whose value would be updated
> while iterating. This is why Lexicon#Get_Term, and TermStepper#Get_Value do
> not have `incremented` return values -- they're conceived as accessors to this
> mutable term.
>
> I think the best approach may be to change those methods to return
> `incremented` values, and that we reorient ourselves to think of them as
> factories rather than accessors.
This would mean to make MatchTermInfoStepper return incremented values, too, resulting in some unnecessary copying of TermInfo objects. My current approach is to keep a reference to the converted String in TextTermStepper:
https://git-wip-us.apache.org/repos/asf?p=lucy.git;a=commitdiff;h=56cbd56c139cd4dfed4bb56f726626ea1092697e
> Perhaps this is an opportunity to simplify some APIs. :D
>
> * Change SortCache#Value to a factory which returns an `incremented` Obj and
> eliminate the `blank` argument.
> * Eliminate SortCache#Make_Blank.
> * It turns out that TextType#Make_Blank and BlobType#Make_Blank are
> unnecessary and can be removed regardless.
I already went that way in this commit:
https://git-wip-us.apache.org/repos/asf?p=lucy.git;a=commitdiff;h=b7881f0e40bf6f5470c8314a5e6aa231817c4cde
> The other is SortFieldWriter#Refill. SortFieldWriter is a pretty hairy
> module. I'd think it would be best to try a minimal approach first and
> benchmark, resorting to major surgery only if absolutely necessary.
Hehe, I realized that when I found out that S_write_files in SortFieldWriter calls Str_Mimic via Obj_Mimic. This commit is probably wrong but I couldn't wrap my head around SortFieldWriter yet:
https://git-wip-us.apache.org/repos/asf?p=lucy.git;a=commitdiff;h=ec1f886752915e4b691c4ae41dd657c47bc3a83c
Nick
Re: [lucy-dev] cfish-string branch
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Tue, Sep 10, 2013 at 3:49 AM, Nick Wellnhofer <we...@aevum.de> wrote:
> On 01/09/2013 22:27, Nick Wellnhofer wrote:
>> I went ahead with this plan in branch cfish-string-prep1.
It's taken a while, but I'm finally caught up with reviewing all the commits
on this branch. I love how it's turning out -- the code using (soon-to-be)
immutable Strings and StringIterators is a substantial improvement over
CharBuf and ZombieCharBuf.
I've got a handful of comments which I'll send in response to individual
commit emails.
>> I'm currently in
>> the middle of step 4 and I identified a few places where immutable strings
>> might have a performance impact:
>>
>> - The `value` field of TextTermStepper
>> - The `value` field of SortCache
>
> This field is mostly used for comparisons with other Strings. If we use a
> CharBuf for the `value` of TextTermStepper, we could avoid most of the
> string copies by adding the following methods:
>
> * TextTermStepper#Compare_Term
> * TextTermStepper#Equals_Term
> * Lexicon#Compare_Term
> * Lexicon#Equals_Term
The root problem with TextTermStepper is that Lexicon was conceived as a
wrapper around a mutable object -- the "term" -- whose value would be updated
while iterating. This is why Lexicon#Get_Term, and TermStepper#Get_Value do
not have `incremented` return values -- they're conceived as accessors to this
mutable term.
I think the best approach may be to change those methods to return
`incremented` values, and that we reorient ourselves to think of them as
factories rather than accessors.
It looks to me like the only inner loop we have that depends on using
Lexicon#Get_Term as a fast accessor is in PolyLexicon, which keeps a
SegLexQueue where SegLexicons are heap-sorted with comparisons powered by
SegLexicon#Get_Term. This could be changed to use cached values a la the
priority queue in ORMatcher (which caches doc IDs in a HeapedMatcherDoc struct
alongside the Matcher which is at that doc ID).
I think all the other sites where Lexicon#Get_Term is used can just be
modified to account for the refcount, because the performance impact of
creating and destroying a String should not be a big deal.
IMO, we should consider this approach because I believe we'll need change
Lexicon#Get_Term anyway. Under the present "accessor" model, there's really
no way to do things except return the inner CharBuf, which isn't going to be
convenient.
> A similar approach could be used for SortCache.
Perhaps this is an opportunity to simplify some APIs. :D
* Change SortCache#Value to a factory which returns an `incremented` Obj and
eliminate the `blank` argument.
* Eliminate SortCache#Make_Blank.
* It turns out that TextType#Make_Blank and BlobType#Make_Blank are
unnecessary and can be removed regardless.
There are two sites which may present performance issues after such changes.
The first is SortCache#Find, which might be most easily fixed with something
like a "SortCache#Compare_Term" method as you suggest.
The other is SortFieldWriter#Refill. SortFieldWriter is a pretty hairy
module. I'd think it would be best to try a minimal approach first and
benchmark, resorting to major surgery only if absolutely necessary.
>> - Function S_write_terms_and_postings in PostingPool
>
> Here we could pass a CharBuf to LexWriter#Add_Term and subsequently to
> TermStepper#Write_*.
I think that makes sense. It seems a little ugly and inconsistent, but unlike
Lexicon#Get_Term and SortCache#Value, these aren't prominent user-facing APIs.
Marvin Humphrey
Re: [lucy-dev] cfish-string branch
Posted by Nick Wellnhofer <we...@aevum.de>.
On 01/09/2013 22:27, Nick Wellnhofer wrote:
>
> I went ahead with this plan in branch cfish-string-prep1. I'm currently in the middle of step 4 and I identified a few places where immutable strings might have a performance impact:
>
> - The `value` field of TextTermStepper
> - The `value` field of SortCache
This field is mostly used for comparisons with other Strings. If we use
a CharBuf for the `value` of TextTermStepper, we could avoid most of the
string copies by adding the following methods:
* TextTermStepper#Compare_Term
* TextTermStepper#Equals_Term
* Lexicon#Compare_Term
* Lexicon#Equals_Term
A similar approach could be used for SortCache.
> - Function S_write_terms_and_postings in PostingPool
Here we could pass a CharBuf to LexWriter#Add_Term and subsequently to
TermStepper#Write_*.
Nick
Re: [lucy-dev] cfish-string branch
Posted by Nick Wellnhofer <we...@aevum.de>.
On Aug 25, 2013, at 19:41 , Nick Wellnhofer <we...@aevum.de> wrote:
> What about this:
>
> 1. Start a new branch.
> 2. Rename CharBuf to String, ZombieCharBuf to StackString.
> 3. Implement new CharBuf class.
> 4. Switch over sites which actually need mutability to CharBuf.
> 5. Remove mutating methods from String, but keep Nip/Chop for ViewCBs.
> 6. Implement StringIterator.
> 7. Switch from ViewCharBufs to StringIterator.
> 8. Remove Nip/Chop and ViewCharBuf.
> 9. Review and rewrite String class now that strings are immutable.
I went ahead with this plan in branch cfish-string-prep1. I'm currently in the middle of step 4 and I identified a few places where immutable strings might have a performance impact:
- The `value` field of TextTermStepper
- The `value` field of SortCache
- Function S_write_terms_and_postings in PostingPool
With immutable string, we'll have to allocate a new String for each term. I'm not sure whether this is acceptable.
Nick
Re: [lucy-dev] cfish-string branch
Posted by Nick Wellnhofer <we...@aevum.de>.
On Aug 25, 2013, at 05:50 , Marvin Humphrey <ma...@rectangular.com> wrote:
> On Fri, Aug 23, 2013 at 3:33 PM, Nick Wellnhofer <we...@aevum.de> wrote:
>> I just saw that you started to work on an immutable string class. It's a
>> good idea to get this done before the first Clownfish release. Some
>> implementation details have already been discussed on lucy-dev and I have an
>> unpublished, local branch where I continued to flesh out the design of
>> string iterators.
>
> Before getting started, I had a look at the published branch
> "string-iterator-wip1":
>
> https://git-wip-us.apache.org/repos/asf?p=lucy.git;a=shortlog;h=refs/heads/string-iterator-wip1
>
> It seems as though source code churn from changes like "_IMP" has made the
> branch impractical to update, so the commits will have to be recreated one by
> one. Nevertheless, the concepts remain just as applicable since the main
> code base has changed only superficially.
This was just an early experiment anyway. My current sketch for the StringIterator class looks like this:
class Clownfish::StringIterator cnick StrIter
inherits Clownfish::Obj {
String *string;
size_t byte_offset;
inert incremented StringIterator*
new(String *string, size_t byte_offset);
/** Return the substring between the top and tail iterators.
* @param offset Offset from the top, in code points.
* @param len The desired length of the substring, in code points.
*/
inert incremented String*
substring(StringIterator *top, StringIterator *tail);
public incremented Obj*
Clone(StringIterator *self);
public void
Assign(StringIterator *self, StringIterator *other);
/** Return true if the iterator is not at the end of the string.
*/
public bool
Has_Next(StringIterator *self);
/** Return true if the iterator is not at the start of the string.
*/
public bool
Has_Prev(StringIterator *self);
/** Return the code point after the current position and advance the
* iterator. Return CFISH_STRITER_DONE at the end of the string.
*/
public uint32_t
Next(StringIterator *self);
/** Return the code point before the current position and go one step back.
* Return CFISH_STRITER_DONE at the start of the string.
*/
public uint32_t
Prev(StringIterator *self);
/** Skip code points.
* @param num The number of code points to skip.
* @return the number of code points actually skipped. This can be less
* than the requested number if the end of the string is reached.
*/
public size_t
Advance(StringIterator *self, size_t num);
/** Skip code points backward.
* @param num The number of code points to skip.
* @return the number of code points actually skipped. This can be less
* than the requested number if the start of the string is reached.
*/
public size_t
Recede(StringIterator *self, size_t num);
/** Skip whitespace.
* @return the number of code points skipped.
*/
public size_t
Skip_Next_Whitespace(StringIterator *self);
/** Skip whitespace backward.
* @return the number of code points skipped.
*/
public size_t
Skip_Prev_Whitespace(StringIterator *self);
/** Test whether the content after the iterator starts with the content
* of a string.
*/
bool
Starts_With(StringIterator *self, String *prefix);
public void
Destroy(StringIterator *self);
}
Some other things that might be useful:
- Peek_Next/Peek_Prev (could replace Has_Next/Has_Prev)
- Keeping track of the character (code point) offset. This is problematic
with string iterators starting from the end of a string unless we add
a field containing the total number of characters to the String class.
> There's a task which isn't on your list which is to my mind perhaps the most
> important: vet the emerging Clownfish String design against existing
> implementations from several other popular programming languages.
>
> I'm concerned about several substandard features of Clownfish, which wormed
> their way into the codebase through expedience, accident, or failed
> experiment, becoming part of the public API. We're better off excising that
> unhealthy tissue sooner rather than later, and comparing Clownfish's design
> against other designs will hopefully allow us to diagnose any problems.
I think one of the worst parts is the use of ViewCharBufs together with Nip/Chop for iteration.
> It would be great to collaborate on creating the best possible immutable
> String class for Clownfish. I suspected you might want to take part, which
> was why I deliberately started off the cfish-string-wip1 branch with only the
> most basic skeleton. :)
Let's get this done, then ;)
> When we're done (enough) with String, if it turns out that piecemeal
> integration is too awkward, there's an alternate path:
>
> 1. Start a new branch.
> 2. Duplicate CharBuf in a new class, CharBuffer.
> 3. Rename CharBuf to String in one huge but superficial.
> 4. Switch over sites which actually need mutability to CharBuffer. There
> aren't that many.
> 5. Replace CharBuf-masquerading-as-String with the actual immutable String
> class completed earlier.
> 6. Rename CharBuffer to CharBuf.
Maybe that's the better approach. What do we gain from making CharBuf a subclass of String temporarily? Also, a major part of the work will be to replace ViewCharBufs with StringIterators. What about this:
1. Start a new branch.
2. Rename CharBuf to String, ZombieCharBuf to StackString.
3. Implement new CharBuf class.
4. Switch over sites which actually need mutability to CharBuf.
5. Remove mutating methods from String, but keep Nip/Chop for ViewCBs.
6. Implement StringIterator.
7. Switch from ViewCharBufs to StringIterator.
8. Remove Nip/Chop and ViewCharBuf.
9. Review and rewrite String class now that strings are immutable.
Nick
Re: [lucy-dev] cfish-string branch
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Fri, Aug 23, 2013 at 3:33 PM, Nick Wellnhofer <we...@aevum.de> wrote:
> I just saw that you started to work on an immutable string class. It's a
> good idea to get this done before the first Clownfish release. Some
> implementation details have already been discussed on lucy-dev and I have an
> unpublished, local branch where I continued to flesh out the design of
> string iterators.
Before getting started, I had a look at the published branch
"string-iterator-wip1":
https://git-wip-us.apache.org/repos/asf?p=lucy.git;a=shortlog;h=refs/heads/string-iterator-wip1
It seems as though source code churn from changes like "_IMP" has made the
branch impractical to update, so the commits will have to be recreated one by
one. Nevertheless, the concepts remain just as applicable since the main
code base has changed only superficially.
> I see that you made CharBuf inherit from String as a temporary measure. It
> seems that you have a plan on how to make a gradual transition to immutable
> strings which would be great. Can you share some details about the separate
> steps so I could help with some of the work?
What I had in mind was to transition classes which make minimal use of
CharBuf's features as early as possible -- e.g. those which store fixed field
names as CharBufs.
However, thinking things through a little more, I'm not sure that migrating
classes from CharBuf to String piecemeal is going to work out so conveniently.
We will probably run into problems because the automatic conversion code in
XSBind.c won't play nice with type mismatches between CharBuf and String.
In that case, the cfish-string-wip1 branch will become a proof-of-concept,
used to firm up the design of String, but not leading to a final outcome via a
straight line sequence of commits.
> From what I understand, the process should roughly look like this:
There's a task which isn't on your list which is to my mind perhaps the most
important: vet the emerging Clownfish String design against existing
implementations from several other popular programming languages.
I'm concerned about several substandard features of Clownfish, which wormed
their way into the codebase through expedience, accident, or failed
experiment, becoming part of the public API. We're better off excising that
unhealthy tissue sooner rather than later, and comparing Clownfish's design
against other designs will hopefully allow us to diagnose any problems.
Removing Dump/Load, Serialize/Deserialize, and Make has been a good start.
There's more to do -- in the context of String, I'm particularly dissatisfied
with the type specifiers in the format used by newf() -- but thank goodness,
now that Clownfish runtime is separate from Lucy and comprises only a handful
of classes, performing a thorough review the API design doesn't feel
unreasonable.
Once upon a time, I imagined that we'd perform such a review after finishing
Python and Ruby bindings but before exposing a C API. I'd hoped that the
community would accumulate collective wisdom through the process of
implementing bindings for multiple dynamic languages and that the experience
would inform our choices while polishing the design of the runtime. But it
turns out that the C bindings were finished first, so here we are. :)
I'll kick things off with a review of String's Starts_With() and Ends_With().
> * Move a couple of methods from CharBuf to String.
> * Implement string iterators.
> * Make CFC convert between Perl and Clownfish strings.
> * Implement a "zombie" string class?
> * Step-by-step conversion of CharBufs to Strings.
> * Make CharBuf a separate class.
It would be great to collaborate on creating the best possible immutable
String class for Clownfish. I suspected you might want to take part, which
was why I deliberately started off the cfish-string-wip1 branch with only the
most basic skeleton. :)
When we're done (enough) with String, if it turns out that piecemeal
integration is too awkward, there's an alternate path:
1. Start a new branch.
2. Duplicate CharBuf in a new class, CharBuffer.
3. Rename CharBuf to String in one huge but superficial.
4. Switch over sites which actually need mutability to CharBuffer. There
aren't that many.
5. Replace CharBuf-masquerading-as-String with the actual immutable String
class completed earlier.
6. Rename CharBuffer to CharBuf.
Marvin Humphrey