ocaml-rope-commit Mailing List for OCaml Rope Library
Brought to you by:
chris_77
You can subscribe to this list here.
2007 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
(12) |
Sep
|
Oct
|
Nov
|
Dec
(2) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2008 |
Jan
(8) |
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
From: ChriS <chr...@us...> - 2008-01-31 22:11:12
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv21053 Modified Files: Makefile all.itarget rope_top.ml Added Files: bench.itarget Log Message: * Added simple web site. Index: rope_top.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope_top.ml,v retrieving revision 1.1.1.1 retrieving revision 1.2 diff -C2 -d -r1.1.1.1 -r1.2 *** rope_top.ml 9 Aug 2007 17:24:56 -0000 1.1.1.1 --- rope_top.ml 31 Jan 2008 22:11:08 -0000 1.2 *************** *** 1,2 **** --- 1,3 ---- + (* #directory "_build";;*) #load "rope.cma";; Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/Makefile,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 *** Makefile 26 Jan 2008 08:34:25 -0000 1.6 --- Makefile 31 Jan 2008 22:11:08 -0000 1.7 *************** *** 50,60 **** # Release a Sourceforge tarball and publish the HTML doc .PHONY: web upload ! web: doc @ if [ -d doc ] ; then \ scp -r doc/ shell.sf.net:$(SF_WEB)/ \ && echo "*** Published documentation on SF" ; \ fi @ if [ -d $(SRC_WEB)/ ] ; then \ ! scp $(SRC_WEB)/*.html $(SRC_WEB)/*.jpg LICENSE \ shell.sf.net:$(SF_WEB) \ && echo "*** Published web site ($(SRC_WEB)/) on SF" ; \ --- 50,61 ---- # Release a Sourceforge tarball and publish the HTML doc .PHONY: web upload ! web-doc: doc @ if [ -d doc ] ; then \ scp -r doc/ shell.sf.net:$(SF_WEB)/ \ && echo "*** Published documentation on SF" ; \ fi + web: @ if [ -d $(SRC_WEB)/ ] ; then \ ! scp $(SRC_WEB)/*.html $(SRC_WEB)/*.css $(SRC_WEB)/*.png LICENSE \ shell.sf.net:$(SF_WEB) \ && echo "*** Published web site ($(SRC_WEB)/) on SF" ; \ Index: all.itarget =================================================================== RCS file: /cvsroot/ocaml-rope/rope/all.itarget,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** all.itarget 16 Jan 2008 06:33:37 -0000 1.1 --- all.itarget 31 Jan 2008 22:11:08 -0000 1.2 *************** *** 1,4 **** rope.cma rope.cmxa - bench/bm_ropes.native - bench/bm_ropes.byte --- 1,2 ---- --- NEW FILE: bench.itarget --- bench/bm_ropes.native bench/bm_ropes.byte |
Update of /cvsroot/ocaml-rope/rope/web In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv21053/web Added Files: LICENSE documentation.png download.png index.html license.png rope.css rope.png summary.png Log Message: * Added simple web site. --- NEW FILE: index.html --- <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html> <head> <meta content="text/html; charset=ISO-8859-1" http-equiv="content-type" /> <title>OCaml Rope module</title> <meta name="author" content="Christophe Troestler" /> <meta name="description" content="Module implementing the rope datastructure" /> <link title="Rope style" rel="stylesheet" href="rope.css" type="text/css"> </head> <body> <br /> <table style="text-align: left; width: 100%;" border="0" cellspacing="2" cellpadding="2"> <tbody> <tr> <td colspan="2" rowspan="1" style="vertical-align: top; width: 18%; text-align: center; white-space: nowrap;" ><img style="width: 800px; height: 111px;" alt="OCaml Rope" src="rope.png" ><br /><br /> </td> </tr> <tr> <td style="vertical-align: top; width: 270px;"> <a href="http://sourceforge.net/projects/ocaml-benchmark/" class="menu" ><img style="border: 0px solid ; width: 167px; height: 44px;" alt="Summary" src="summary.png"></a><br/> <a href="doc/Rope.html" class="menu" ><img style="border: 0px solid ; width: 264px; height: 44px;" alt="Documentation" src="documentation.png"></a><br/> <a href="http://sourceforge.net/project/showfiles.php?group_id=202934" class="menu" ><img style="border: 0px solid ; width: 174px; height: 44px;" alt="Download" src="download.png"></a><br> <a href="LICENSE" class="menu" ><img style="border: 0px solid ; width: 132px; height: 44px;" alt="License" src="license.png"></a> </td> <td style="vertical-align: top;"> <p> As its name implies, the OCaml Rope library implements the immutable <a href="http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf">rope datastructure</a> [1] (with some small variations). All meaningful <code>String</code> module functions are implemented; regular expressions are planned (help appreciated). </p> <p> Here is an example use of <code>Rope</code> in the interactive toploop (notice the special printer to conveniently display ropes):<br/> <pre><code class="ocaml" ><span class="prompt">#</span> <span class="input">#load "rope.cma"</span>;; <span class="prompt">#</span> <span class="input">#install_printer <span class="module">Rope</span>.<span class="module">Rope_toploop</span>.printer</span>;; <span class="prompt">#</span> <span class="input"><span class="let">let</span> ( ^ ) = Rope.concat2</span>;; <span class="answer">val ( ^ ) : Rope.t -> Rope.t -> Rope.t = <fun></span> <span class="prompt">#</span> <span class="input"><span class="let">let</span> r = <span class="module">Rope</span>.of_string "Hello" ^ <span class="module">Rope</span>.of_string " " ^ <span class="module">Rope</span>.of_string "world!"</span>;; <span class="answer">val r : Rope.t = "Hello world!"</span> <span class="prompt">#</span> <span class="input"><span class="module">Rope</span>.length r</span>;; <span class="answer">- : int = 12</span></code></pre> For a complete description of the functions, see the interface <a href="doc/Rope.html"><code>Rope.mli</code></a>. If you have questions, suggestions, bugs,... you can contact me by email: <a href="mailto:chr...@us...?SUBJECT=OCaml%20Rope">chr...@us...</a><br> <p> The code is released under the GNU Lesser General Public License (LGPL) with the same special exception as for the OCaml standard library (see the file <a href="LICENSE">LICENSE</a> for more details). </p> <br/> <hr width="10%" align="left" /> <p>[1] Hans Boehm, Russ Atkinson, Michael Plass, "Ropes: an alternative to strings", Software Practice and Experience 25, vol. 12 (1995), pp. 1315-1330. </p> </td> </tr> </tbody> </table> <br/><br/><br/><br/> <a href="http://sourceforge.net" ><img src="http://sflogo.sourceforge.net/sflogo.php?group_id=202934&type=2" width="125" height="37" border="0" alt="SourceForge.net Logo" /></a> </body> </html> --- NEW FILE: summary.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: LICENSE --- This Library is distributed under the terms of the GNU Lesser General Public License version 2.1 (included below) or, at your choice, any later version. As a special exception to the GNU Lesser General Public License, you may link, statically or dynamically, a "work that uses the Library" with a publicly distributed version of the Library to produce an executable file containing portions of the Library, and distribute that executable file under terms of your choice, without any of the additional requirements listed in clause 6 of the GNU Lesser General Public License. By "a publicly distributed version of the Library", we mean either the unmodified Library as distributed, or a modified version of the Library that is distributed under the conditions defined in clause 3 of the GNU Library General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU Lesser General Public License. GNU LESSER GENERAL PUBLIC LICENSE Version 2.1, February 1999 Copyright (C) 1991, 1999 Free Software Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. [This is the first released version of the Lesser GPL. It also counts as the successor of the GNU Library Public License, version 2, hence the version number 2.1.] Preamble The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public Licenses are intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This license, the Lesser General Public License, applies to some specially designated software packages--typically libraries--of the Free Software Foundation and other authors who decide to use it. You can use it too, but we suggest you first think carefully about whether this license or the ordinary General Public License is the better strategy to use in any particular case, based on the explanations below. When we speak of free software, we are referring to freedom of use, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish); that you receive source code or can get it if you want it; that you can change the software and use pieces of it in new free programs; and that you are informed that you can do these things. To protect your rights, we need to make restrictions that forbid distributors to deny you these rights or to ask you to surrender these rights. These restrictions translate to certain responsibilities for you if you distribute copies of the library or if you modify it. For example, if you distribute copies of the library, whether gratis or for a fee, you must give the recipients all the rights that we gave you. You must make sure that they, too, receive or can get the source code. If you link other code with the library, you must provide complete object files to the recipients, so that they can relink them with the library after making changes to the library and recompiling it. And you must show them these terms so they know their rights. We protect your rights with a two-step method: (1) we copyright the library, and (2) we offer you this license, which gives you legal permission to copy, distribute and/or modify the library. To protect each distributor, we want to make it very clear that there is no warranty for the free library. Also, if the library is modified by someone else and passed on, the recipients should know that what they have is not the original version, so that the original author's reputation will not be affected by problems that might be introduced by others. Finally, software patents pose a constant threat to the existence of any free program. We wish to make sure that a company cannot effectively restrict the users of a free program by obtaining a restrictive license from a patent holder. Therefore, we insist that any patent license obtained for a version of the library must be consistent with the full freedom of use specified in this license. Most GNU software, including some libraries, is covered by the ordinary GNU General Public License. This license, the GNU Lesser General Public License, applies to certain designated libraries, and is quite different from the ordinary General Public License. We use this license for certain libraries in order to permit linking those libraries into non-free programs. When a program is linked with a library, whether statically or using a shared library, the combination of the two is legally speaking a combined work, a derivative of the original library. The ordinary General Public License therefore permits such linking only if the entire combination fits its criteria of freedom. The Lesser General Public License permits more lax criteria for linking other code with the library. We call this license the "Lesser" General Public License because it does Less to protect the user's freedom than the ordinary General Public License. It also provides other free software developers Less of an advantage over competing non-free programs. These disadvantages are the reason we use the ordinary General Public License for many libraries. However, the Lesser license provides advantages in certain special circumstances. For example, on rare occasions, there may be a special need to encourage the widest possible use of a certain library, so that it becomes a de-facto standard. To achieve this, non-free programs must be allowed to use the library. A more frequent case is that a free library does the same job as widely used non-free libraries. In this case, there is little to gain by limiting the free library to free software only, so we use the Lesser General Public License. In other cases, permission to use a particular library in non-free programs enables a greater number of people to use a large body of free software. For example, permission to use the GNU C Library in non-free programs enables many more people to use the whole GNU operating system, as well as its variant, the GNU/Linux operating system. Although the Lesser General Public License is Less protective of the users' freedom, it does ensure that the user of a program that is linked with the Library has the freedom and the wherewithal to run that program using a modified version of the Library. The precise terms and conditions for copying, distribution and modification follow. Pay close attention to the difference between a "work based on the library" and a "work that uses the library". The former contains code derived from the library, whereas the latter must be combined with the library in order to run. GNU LESSER GENERAL PUBLIC LICENSE TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 0. This License Agreement applies to any software library or other program which contains a notice placed by the copyright holder or other authorized party saying it may be distributed under the terms of this Lesser General Public License (also called "this License"). Each licensee is addressed as "you". A "library" means a collection of software functions and/or data prepared so as to be conveniently linked with application programs (which use some of those functions and data) to form executables. The "Library", below, refers to any such software library or work which has been distributed under these terms. A "work based on the Library" means either the Library or any derivative work under copyright law: that is to say, a work containing the Library or a portion of it, either verbatim or with modifications and/or translated straightforwardly into another language. (Hereinafter, translation is included without limitation in the term "modification".) "Source code" for a work means the preferred form of the work for making modifications to it. For a library, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the library. Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running a program using the Library is not restricted, and output from such a program is covered only if its contents constitute a work based on the Library (independent of the use of the Library in a tool for writing it). Whether that is true depends on what the Library does and what the program that uses the Library does. 1. You may copy and distribute verbatim copies of the Library's complete source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and distribute a copy of this License along with the Library. You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee. 2. You may modify your copy or copies of the Library or any portion of it, thus forming a work based on the Library, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions: a) The modified work must itself be a software library. b) You must cause the files modified to carry prominent notices stating that you changed the files and the date of any change. c) You must cause the whole of the work to be licensed at no charge to all third parties under the terms of this License. d) If a facility in the modified Library refers to a function or a table of data to be supplied by an application program that uses the facility, other than as an argument passed when the facility is invoked, then you must make a good faith effort to ensure that, in the event an application does not supply such function or table, the facility still operates, and performs whatever part of its purpose remains meaningful. (For example, a function in a library to compute square roots has a purpose that is entirely well-defined independent of the application. Therefore, Subsection 2d requires that any application-supplied function or table used by this function must be optional: if the application does not supply it, the square root function must still compute square roots.) These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Library, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Library, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it. Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Library. In addition, mere aggregation of another work not based on the Library with the Library (or with a work based on the Library) on a volume of a storage or distribution medium does not bring the other work under the scope of this License. 3. You may opt to apply the terms of the ordinary GNU General Public License instead of this License to a given copy of the Library. To do this, you must alter all the notices that refer to this License, so that they refer to the ordinary GNU General Public License, version 2, instead of to this License. (If a newer version than version 2 of the ordinary GNU General Public License has appeared, then you can specify that version instead if you wish.) Do not make any other change in these notices. Once this change is made in a given copy, it is irreversible for that copy, so the ordinary GNU General Public License applies to all subsequent copies and derivative works made from that copy. This option is useful when you wish to copy part of the code of the Library into a program that is not a library. 4. You may copy and distribute the Library (or a portion or derivative of it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange. If distribution of object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place satisfies the requirement to distribute the source code, even though third parties are not compelled to copy the source along with the object code. 5. A program that contains no derivative of any portion of the Library, but is designed to work with the Library by being compiled or linked with it, is called a "work that uses the Library". Such a work, in isolation, is not a derivative work of the Library, and therefore falls outside the scope of this License. However, linking a "work that uses the Library" with the Library creates an executable that is a derivative of the Library (because it contains portions of the Library), rather than a "work that uses the library". The executable is therefore covered by this License. Section 6 states terms for distribution of such executables. When a "work that uses the Library" uses material from a header file that is part of the Library, the object code for the work may be a derivative work of the Library even though the source code is not. Whether this is true is especially significant if the work can be linked without the Library, or if the work is itself a library. The threshold for this to be true is not precisely defined by law. If such an object file uses only numerical parameters, data structure layouts and accessors, and small macros and small inline functions (ten lines or less in length), then the use of the object file is unrestricted, regardless of whether it is legally a derivative work. (Executables containing this object code plus portions of the Library will still fall under Section 6.) Otherwise, if the work is a derivative of the Library, you may distribute the object code for the work under the terms of Section 6. Any executables containing that work also fall under Section 6, whether or not they are linked directly with the Library itself. 6. As an exception to the Sections above, you may also combine or link a "work that uses the Library" with the Library to produce a work containing portions of the Library, and distribute that work under terms of your choice, provided that the terms permit modification of the work for the customer's own use and reverse engineering for debugging such modifications. You must give prominent notice with each copy of the work that the Library is used in it and that the Library and its use are covered by this License. You must supply a copy of this License. If the work during execution displays copyright notices, you must include the copyright notice for the Library among them, as well as a reference directing the user to the copy of this License. Also, you must do one of these things: a) Accompany the work with the complete corresponding machine-readable source code for the Library including whatever changes were used in the work (which must be distributed under Sections 1 and 2 above); and, if the work is an executable linked with the Library, with the complete machine-readable "work that uses the Library", as object code and/or source code, so that the user can modify the Library and then relink to produce a modified executable containing the modified Library. (It is understood that the user who changes the contents of definitions files in the Library will not necessarily be able to recompile the application to use the modified definitions.) b) Use a suitable shared library mechanism for linking with the Library. A suitable mechanism is one that (1) uses at run time a copy of the library already present on the user's computer system, rather than copying library functions into the executable, and (2) will operate properly with a modified version of the library, if the user installs one, as long as the modified version is interface-compatible with the version that the work was made with. c) Accompany the work with a written offer, valid for at least three years, to give the same user the materials specified in Subsection 6a, above, for a charge no more than the cost of performing this distribution. d) If distribution of the work is made by offering access to copy from a designated place, offer equivalent access to copy the above specified materials from the same place. e) Verify that the user has already received a copy of these materials or that you have already sent this user a copy. For an executable, the required form of the "work that uses the Library" must include any data and utility programs needed for reproducing the executable from it. However, as a special exception, the materials to be distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable. It may happen that this requirement contradicts the license restrictions of other proprietary libraries that do not normally accompany the operating system. Such a contradiction means you cannot use both them and the Library together in an executable that you distribute. 7. You may place library facilities that are a work based on the Library side-by-side in a single library together with other library facilities not covered by this License, and distribute such a combined library, provided that the separate distribution of the work based on the Library and of the other library facilities is otherwise permitted, and provided that you do these two things: a) Accompany the combined library with a copy of the same work based on the Library, uncombined with any other library facilities. This must be distributed under the terms of the Sections above. b) Give prominent notice with the combined library of the fact that part of it is a work based on the Library, and explaining where to find the accompanying uncombined form of the same work. 8. You may not copy, modify, sublicense, link with, or distribute the Library except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense, link with, or distribute the Library is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 9. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Library or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Library (or any work based on the Library), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Library or works based on it. 10. Each time you redistribute the Library (or any work based on the Library), the recipient automatically receives a license from the original licensor to copy, distribute, link with or modify the Library subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties with this License. 11. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Library at all. For example, if a patent license would not permit royalty-free redistribution of the Library by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Library. If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply, and the section as a whole is intended to apply in other circumstances. It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice. This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License. 12. If the distribution and/or use of the Library is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Library under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License. 13. The Free Software Foundation may publish revised and/or new versions of the Lesser General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. Each version is given a distinguishing version number. If the Library specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Library does not specify a license version number, you may choose any version ever published by the Free Software Foundation. 14. If you wish to incorporate parts of the Library into other free programs whose distribution conditions are incompatible with these, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally. NO WARRANTY 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. END OF TERMS AND CONDITIONS How to Apply These Terms to Your New Libraries If you develop a new library, and you want it to be of the greatest possible use to the public, we recommend making it free software that everyone can redistribute and change. You can do so by permitting redistribution under these terms (or, alternatively, under the terms of the ordinary General Public License). To apply these terms, attach the following notices to the library. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the "copyright" line and a pointer to where the full notice is found. <one line to give the library's name and a brief idea of what it does.> Copyright (C) <year> <name of author> This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Also add information on how to contact you by electronic and paper mail. You should also get your employer (if you work as a programmer) or your school, if any, to sign a "copyright disclaimer" for the library, if necessary. Here is a sample; alter the names: Yoyodyne, Inc., hereby disclaims all copyright interest in the library `Frob' (a library for tweaking knobs) written by James Random Hacker. <signature of Ty Coon>, 1 April 1990 Ty Coon, President of Vice That's all there is to it! --- NEW FILE: license.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: download.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: documentation.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: rope.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: rope.css --- A:active { color: #ff6600; } A:visited { color: #999999; } /*** * Code */ code.ocaml { display: block; /* font-size: large; */ background-color: rgb(240,245,254); padding: 5px; } .prompt { color: rgb(128,128,128); } .let { font-weight: bold; } .module { color: rgb(126,27,29); } span.input:hover { background-color: rgb(200,200,200); } .answer { font-style: italic; } span.answer:hover { background-color: rgb(200,200,200); } /*** * Menu */ a.menu img:hover { background-color: rgb(200,200,200); } /* General */ body { color: black; background-color: rgb(255,255,255); } A:link { color: rgb(126,27,29); } |
From: ChriS <chr...@us...> - 2008-01-31 22:04:58
|
Update of /cvsroot/ocaml-rope/rope/web In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv18664/web Log Message: Directory /cvsroot/ocaml-rope/rope/web added to the repository |
From: ChriS <chr...@us...> - 2008-01-26 08:34:25
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv30445/bench Modified Files: bm_ropes.ml bm_ropes.plot Log Message: - Added a quicksort benchmark comparison. Index: bm_ropes.plot =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.plot,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** bm_ropes.plot 25 Dec 2007 03:06:32 -0000 1.5 --- bm_ropes.plot 26 Jan 2008 08:34:25 -0000 1.6 *************** *** 75,78 **** --- 75,99 ---- unset logscale x + if (hardcopy) set output "qsort.png"; else set terminal wxt 4 raise + set multiplot layout 2,1 downwards + set key top left + set title "Min. unitary random qsort time" + plot \ + "qsort.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ + "qsort.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ + "qsort.dat" using 1:6 with lines title "Tiny (balanced)", \ + "qsort.dat" using 1:8 with lines title "FullFeatured (balanced)" + set title "" + set ylabel "depth (average after sub)" + plot \ + "qsort.dat" using 1:3 with linespoints title "Tiny (unbalanced)", \ + "qsort.dat" using 1:5 with linespoints title "FullFeatured (unbalanced)", \ + "qsort.dat" using 1:7 with lines title "Tiny (balanced)", \ + "qsort.dat" using 1:9 with lines title "FullFeatured (balanced)" + unset multiplot + unset logscale x + + + # Local Variables: # mode: gnuplot Index: bm_ropes.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.ml,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** bm_ropes.ml 25 Dec 2007 03:06:32 -0000 1.5 --- bm_ropes.ml 26 Jan 2008 08:34:25 -0000 1.6 *************** *** 50,54 **** let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in Array.concat (List.map pow10_of basis (*@ [ [|max_int / 2 |] } *) ) ! (* FIXME: for max_int, TinyRope segfaults!!! *) let datapoints2 = --- 50,54 ---- let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in Array.concat (List.map pow10_of basis (*@ [ [|max_int / 2 |] } *) ) ! (* FIXME: for max_int (32 bits), TinyRope segfaults!!! *) let datapoints2 = *************** *** 105,109 **** module IMap = Map.Make(struct type t = int let compare = compare end) ! module Benchmark(M : sig type t --- 105,109 ---- module IMap = Map.Make(struct type t = int let compare = compare end) ! module Benchmark(R : sig type t *************** *** 119,122 **** --- 119,124 ---- val get : t -> int -> char val sub : t -> int -> int -> t + val of_string : string -> t + val to_string : t -> string end) = struct *************** *** 128,150 **** let rec add_chars r c size = if size <= 0 then r else ! let op = if size land prepend_size = 0 then M.prepend else M.append in add_chars (op c r) c (size - 1) in let rec build nconcat r size = let largest = IMap.fold (fun _ v s -> ! let len = M.length v in ! if len > M.length s && len <= size then v else s ! ) !rope_tbl M.empty in ! if M.length largest = 0 || nconcat > max_nconcat then (* no piece to add to [r] *) ! add_chars r 'x' (size - M.length largest) else let r' = ! if Random.bool() then M.concat r largest else M.concat largest r in ! build (nconcat + 1) r' (size - M.length largest) in fun size -> ! let r = build 0 M.empty size in rope_tbl := IMap.add size r !rope_tbl; ! if M.balanced then M.balance r else r ;; --- 130,152 ---- let rec add_chars r c size = if size <= 0 then r else ! let op = if size land prepend_size = 0 then R.prepend else R.append in add_chars (op c r) c (size - 1) in let rec build nconcat r size = let largest = IMap.fold (fun _ v s -> ! let len = R.length v in ! if len > R.length s && len <= size then v else s ! ) !rope_tbl R.empty in ! if R.length largest = 0 || nconcat > max_nconcat then (* no piece to add to [r] *) ! add_chars r 'x' (size - R.length largest) else let r' = ! if Random.bool() then R.concat r largest else R.concat largest r in ! build (nconcat + 1) r' (size - R.length largest) in fun size -> ! let r = build 0 R.empty size in rope_tbl := IMap.add size r !rope_tbl; ! if R.balanced then R.balance r else r ;; *************** *** 153,164 **** let t0 = Unix.gettimeofday () in for i = 0 to n_ops - 1 do ! v := M.append 'z' !v; (* ignore (append_f I !v); *) done; let dt = (Unix.gettimeofday () -. t0) in ! (dt -. basic_loop_overhead) /. (float_of_int n_ops), M.height !v let measure_append_time size = ! let msg = sprintf "Append time for %s of size %d\n%!" M.name size in sample msg append_time size --- 155,166 ---- let t0 = Unix.gettimeofday () in for i = 0 to n_ops - 1 do ! v := R.append 'z' !v; (* ignore (append_f I !v); *) done; let dt = (Unix.gettimeofday () -. t0) in ! (dt -. basic_loop_overhead) /. (float_of_int n_ops), R.height !v let measure_append_time size = ! let msg = sprintf "Append time for %s of size %d\n%!" R.name size in sample msg append_time size *************** *** 170,181 **** (* let sum = ref 0 in *) for i = 0 to n_ops - 1 do ! ignore(M.get r (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in ! (dt -. random_loop_overhead) /. float n_ops, M.height r ! (* float !sum /. float n_ops, M.height r *) let measure_random_get_time size = ! let msg = sprintf "Random get time for %s of size %d\n%!" M.name size in sample msg random_get_time size --- 172,183 ---- (* let sum = ref 0 in *) for i = 0 to n_ops - 1 do ! ignore(R.get r (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in ! (dt -. random_loop_overhead) /. float n_ops, R.height r ! (* float !sum /. float n_ops, R.height r *) let measure_random_get_time size = ! let msg = sprintf "Random get time for %s of size %d\n%!" R.name size in sample msg random_get_time size *************** *** 186,190 **** let h = ref 0 in for i = 0 to n_ops - 1 do ! h := !h + M.height(M.sub r 0 (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in --- 188,192 ---- let h = ref 0 in for i = 0 to n_ops - 1 do ! h := !h + R.height(R.sub r 0 (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in *************** *** 193,211 **** let measure_sub_time size = ! let msg = sprintf "Sub time for %s of size %d\n%!" M.name size in sample msg sub_time size end module TinyBM = struct - type t = TinyRope.t let name = "TinyRope" ! let empty = TinyRope.empty let append = TinyRope.append_char let prepend = TinyRope.prepend_char - let concat = TinyRope.concat - let length = TinyRope.length - let height = TinyRope.height - let balance = TinyRope.balance let get r i = TinyRope.get i r let sub r start len = TinyRope.sub start len r --- 195,250 ---- let measure_sub_time size = ! let msg = sprintf "Sub time for %s of size %d\n%!" R.name size in sample msg sub_time size + + (* Test inspired by http://www.rubyquiz.com/quiz137.html *) + let size = 512 * 1024 + let size8 = 8 + size + (* [text] is make of [nchunks] chunks of text, each of [size] bytes + long. Each chunck starts with an 8 byte number. Initially the + chuncks are shuffled the this function sorts them into ascending + order. *) + let rec qsort text = + if R.length text = 0 then text else begin + let pivot = int_of_string(R.to_string(R.sub text 0 8)) in + let less = ref R.empty + and more = ref R.empty in + let offset = ref size8 in + while !offset < R.length text do + let i = int_of_string(R.to_string(R.sub text !offset 8)) in + if i < pivot then + less := R.concat !less (R.sub text !offset size8) + else + more := R.concat !more (R.sub text !offset size8); + offset := !offset + 8 + size; + done; + R.concat (qsort !less) (R.concat (R.sub text 0 size8) (qsort !more)) + end + + let bulk_string = make_rope size + let do_qsort size = + let nchunks = size / 100_000 in + let data = ref R.empty in + for i = 1 to nchunks do + data := R.concat !data + (R.concat (R.of_string(sprintf "%08i" (Random.int nchunks))) + bulk_string) + done; + let t0 = Unix.gettimeofday () in + let sorted = qsort !data in + let dt = (Unix.gettimeofday () -. t0) in + (dt -. random_loop_overhead) /. float n_ops, R.height sorted + + let measure_qsort size = + let msg = sprintf "Qsort time for %s of size %d\n%!" R.name size in + sample msg do_qsort size end module TinyBM = struct let name = "TinyRope" ! include TinyRope let append = TinyRope.append_char let prepend = TinyRope.prepend_char let get r i = TinyRope.get i r let sub r start len = TinyRope.sub start len r *************** *** 214,228 **** module FullBM = struct - type t = Rope.t let name = "Rope" ! let empty = Rope.empty let append c r = Rope.concat2 r (Rope.of_char c) let prepend c r = Rope.concat2 (Rope.of_char c) r let concat = Rope.concat2 - let length = Rope.length - let height = Rope.height - let balance = Rope.balance - let get = Rope.get - let sub = Rope.sub end --- 253,261 ---- module FullBM = struct let name = "Rope" ! include Rope let append c r = Rope.concat2 r (Rope.of_char c) let prepend c r = Rope.concat2 (Rope.of_char c) r let concat = Rope.concat2 end *************** *** 269,272 **** --- 302,310 ---- BalancedTinyBM.measure_sub_time; BalancedFullBM.measure_sub_time ]; + Gc.full_major (); + benchmark "qsort.dat" [UnbalancedTinyBM.measure_qsort; + UnbalancedFullBM.measure_qsort; + BalancedTinyBM.measure_qsort; + BalancedFullBM.measure_qsort ]; () |
From: ChriS <chr...@us...> - 2008-01-26 08:34:25
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv30445 Modified Files: Makefile rope.ml Log Message: - Added a quicksort benchmark comparison. Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.10 retrieving revision 1.11 diff -C2 -d -r1.10 -r1.11 *** rope.ml 16 Jan 2008 06:33:37 -0000 1.10 --- rope.ml 26 Jan 2008 08:34:25 -0000 1.11 *************** *** 26,31 **** (* TODO: - Camomille interop. (with phantom types for encoding ??) ! *) --- 26,34 ---- (* TODO: + - Regexp (maybe using Jérôme Vouillon regexp lib ? + http://www.pps.jussieu.fr/~vouillon/) + - Camomille interop. (with phantom types for encoding ??) ! *) *************** *** 1169,1170 **** --- 1172,1179 ---- end + + + + (* Local Variables: *) + (* compile-command: "ocamlbuild -classic-display all.otarget" *) + (* End: *) Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/Makefile,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** Makefile 16 Jan 2008 23:44:02 -0000 1.5 --- Makefile 26 Jan 2008 08:34:25 -0000 1.6 *************** *** 62,70 **** upload: dist ! @ if [ -z "$(PKG_TARBALL)" ]; then \ echo "PKG_TARBALL not defined"; exit 1; fi ! echo -e "bin\ncd incoming\nput $(PKG_TARBALL)" \ | ncftp -p chr...@us... upload.sourceforge.net \ ! && echo "*** Uploaded $(PKG_TARBALL) to SF" --- 62,70 ---- upload: dist ! @ if [ -z "$(TARBALL)" ]; then \ echo "PKG_TARBALL not defined"; exit 1; fi ! echo -e "bin\ncd incoming\nput $(TARBALL)" \ | ncftp -p chr...@us... upload.sourceforge.net \ ! && echo "*** Uploaded $(TARBALL) to SF" |
From: ChriS <chr...@us...> - 2008-01-16 23:43:59
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv20304 Modified Files: Makefile rope.mli Added Files: META.in Log Message: - Added VERSION in rope.mli - META file. --- NEW FILE: META.in --- # Specifications for the Rope module -*-conf-*- # $Id: META.in,v 1.1 2008/01/16 23:44:02 chris_77 Exp $ name="rope" description="OCaml Rope module" requires="" archive(byte)="rope.cma" archive(native)="rope.cmxa" Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/Makefile,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** Makefile 11 Aug 2007 11:16:59 -0000 1.4 --- Makefile 16 Jan 2008 23:44:02 -0000 1.5 *************** *** 1,3 **** ! VERSION=0.2 SF_WEB = /home/groups/o/oc/ocaml-rope/htdocs SRC_WEB = web --- 1,4 ---- ! VERSION = $(shell grep "@version" rope.mli | \ ! sed -r -e "s/[^0-9.]*([0-9.]+).*/\1/") SF_WEB = /home/groups/o/oc/ocaml-rope/htdocs SRC_WEB = web *************** *** 9,13 **** DIST_FILES=rope.ml rope.mli rope_top.ml LICENSE Makefile ! TARBALL_DIR=data-struct-$(VERSION) TARBALL=$(TARBALL_DIR).tar.bz2 --- 10,14 ---- DIST_FILES=rope.ml rope.mli rope_top.ml LICENSE Makefile ! TARBALL_DIR=rope-$(VERSION) TARBALL=$(TARBALL_DIR).tar.bz2 *************** *** 31,34 **** --- 32,39 ---- cd bench; $(MAKE) byte + META: META.in + cp $^ $@ + echo "version=\"$(VERSION)\"" >> $@ + doc: $(wildcard *.mli) [ -d "$@" ] || mkdir $@ *************** *** 103,108 **** .PHONY: clean clean:: ! $(RM) -f *.cm{i,o,x,a,xa} *.annot *.o *.a *~ ! rm -rf doc/ find . -type f -perm -u=x -exec rm -f {} \; cd bench; $(MAKE) clean \ No newline at end of file --- 108,113 ---- .PHONY: clean clean:: ! $(RM) -f *.cm{i,o,x,a,xa} *.annot *.o *.a *~ META _log $(TARBALL) ! rm -rf doc/ _build/ find . -type f -perm -u=x -exec rm -f {} \; cd bench; $(MAKE) clean \ No newline at end of file Index: rope.mli =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.mli,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** rope.mli 11 Aug 2007 01:15:16 -0000 1.3 --- rope.mli 16 Jan 2008 23:44:02 -0000 1.4 *************** *** 50,53 **** --- 50,54 ---- @author Christophe Troestler + @version 0.3 *) |
From: ChriS <chr...@us...> - 2008-01-16 23:43:59
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv20304/bench Modified Files: .depend.ocaml Log Message: - Added VERSION in rope.mli - META file. Index: .depend.ocaml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/.depend.ocaml,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** .depend.ocaml 25 Dec 2007 03:06:32 -0000 1.2 --- .depend.ocaml 16 Jan 2008 23:44:02 -0000 1.3 *************** *** 1,2 **** --- 1,4 ---- + bm_ropes.cmo: tinyRope.cmi + bm_ropes.cmx: tinyRope.cmx tinyRope.cmo: tinyRope.cmi tinyRope.cmx: tinyRope.cmi |
From: ChriS <chr...@us...> - 2008-01-16 06:33:35
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv1337 Modified Files: .cvsignore rope.ml Added Files: _tags all.itarget Log Message: - Added all.itarget for ocamlbuild. - Added _tag file for the benchmarks. Index: .cvsignore =================================================================== RCS file: /cvsroot/ocaml-rope/rope/.cvsignore,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** .cvsignore 11 Aug 2007 11:16:59 -0000 1.2 --- .cvsignore 16 Jan 2008 06:33:37 -0000 1.3 *************** *** 6,7 **** --- 6,9 ---- *.cmxa doc + _build + _log Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 *** rope.ml 25 Dec 2007 03:06:32 -0000 1.9 --- rope.ml 16 Jan 2008 06:33:37 -0000 1.10 *************** *** 96,100 **** with Exit -> m, !i ! let rebalancing_height = 43 (* max_height - 1 *) (** Beyond this height, implicit balance will be done. This value allows gross inefficiencies while not being too time consuming. --- 96,100 ---- with Exit -> m, !i ! let rebalancing_height = max_height - 1 (** Beyond this height, implicit balance will be done. This value allows gross inefficiencies while not being too time consuming. --- NEW FILE: all.itarget --- rope.cma rope.cmxa bench/bm_ropes.native bench/bm_ropes.byte --- NEW FILE: _tags --- "bench/bm_ropes.native": use_unix "bench/bm_ropes.byte": use_unix |
From: ChriS <chr...@us...> - 2007-12-25 03:06:29
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv11911 Modified Files: rope.ml Log Message: - Corrected bug in [index] (thanks to Harmen for reporting it) and [rindex]. Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 *** rope.ml 11 Aug 2007 11:24:36 -0000 1.8 --- rope.ml 25 Dec 2007 03:06:32 -0000 1.9 *************** *** 60,64 **** let max_flatten_length = 1024 ! (** When deciding whther to flatten a rope, only those if length [<= max_flatten_length] will be. *) --- 60,64 ---- let max_flatten_length = 1024 ! (** When deciding whether to flatten a rope, only those with length [<= max_flatten_length] will be. *) *************** *** 72,79 **** same order as [max_flatten_length]. *) - let max_relocate_height = 35 - (** Only try to relocate rop leaves if the height of the tree is - less or equal to this value. *) - (* Fibonacci numbers $F_{n+2}$. By definition, a NON-EMPTY rope [r] is balanced iff [length r >= min_length.(height r)]. --- 72,75 ---- *************** *** 100,108 **** with Exit -> m, !i ! let rebalancing_height = max_height - 1 ! (* Beyond this height, implicit balance will be done. This value ! allows gross inefficiencies while not being too time consuming. ! For example, explicit rebalancing did not improve the running ! time on the ICFP 2007 task. *) let empty = Sub("", 0, 0) --- 96,104 ---- with Exit -> m, !i ! let rebalancing_height = 43 (* max_height - 1 *) ! (** Beyond this height, implicit balance will be done. This value ! allows gross inefficiencies while not being too time consuming. ! For example, explicit rebalancing did not really improve the ! running time on the ICFP 2007 task. *) let empty = Sub("", 0, 0) *************** *** 124,128 **** | _ -> true ! (* For debugging and judging the balancing *) let print = let rec map_left = function --- 120,124 ---- | _ -> true ! (* For debugging purposes and judging the balancing *) let print = let rec map_left = function *************** *** 340,344 **** | Sub(_,_,_) -> failwith "Rope.relocate_topright" | Concat(h, len, l,ll, r) -> - if h > max_relocate_height then failwith "Rope.relocate_topright"; let hr = height r + 1 in if hr < h then --- 336,339 ---- *************** *** 354,358 **** | Sub(_,_,_) -> failwith "Rope.relocate_topleft" | Concat(h, len, l,ll, r) -> - if h > max_relocate_height then failwith "Rope.relocate_topleft"; let hl = height l + 1 in if hl < h then --- 349,352 ---- *************** *** 446,455 **** Concat(h2, len, left, lens, r2) end ! | _,_ -> let len1 = length rope1 and len2 = length rope2 in let len = len1 + len2 in (* Small unbalanced ropes may happen if one concat left, then ! right, then left,.. *) if len <= small_rope_length then let s = String.create len in --- 440,450 ---- Concat(h2, len, left, lens, r2) end ! | _, _ -> let len1 = length rope1 and len2 = length rope2 in let len = len1 + len2 in (* Small unbalanced ropes may happen if one concat left, then ! right, then left,... This costs a bit of time but is a good ! defense. *) if len <= small_rope_length then let s = String.create len in *************** *** 490,498 **** ***********************************************************************) let rec sub_to_substring flat j i len = function | Sub(s, i0, lens) -> assert(i >= 0 && i <= lens - len); assert(j >= 0 && j + len <= String.length flat); ! String.blit s (i0 + i) flat j len | Concat(_, rope_len, l, ll, r) -> let ri = i - ll in --- 485,495 ---- ***********************************************************************) + (** [sub_to_substring flat j i len r] copies the subrope of [r] + starting at character [i] and of length [len] to [flat.[j ..]]. *) let rec sub_to_substring flat j i len = function | Sub(s, i0, lens) -> assert(i >= 0 && i <= lens - len); assert(j >= 0 && j + len <= String.length flat); ! String.unsafe_blit s (i0 + i) flat j len | Concat(_, rope_len, l, ll, r) -> let ri = i - ll in *************** *** 567,574 **** else index_string offset s (i+1) i1 c;; ! (* Return the index of [c] from [i] in the rope or a negative value ! if not found *) let rec unsafe_index offset i c = function ! | Sub(s, i0, len) -> index_string offset s i (i0 + len) c | Concat(_, _, l,ll, r) -> if i >= ll then unsafe_index (offset + ll) (i - ll) c r --- 564,572 ---- else index_string offset s (i+1) i1 c;; ! (* Return the index of [c] from position [i] in the rope or a negative ! value if not found *) let rec unsafe_index offset i c = function ! | Sub(s, i0, len) -> ! index_string (offset - i0) s (i0 + i) (i0 + len) c | Concat(_, _, l,ll, r) -> if i >= ll then unsafe_index (offset + ll) (i - ll) c r *************** *** 600,604 **** let rec unsafe_rindex offset i c = function ! | Sub(s, i0, _) -> rindex_string offset s i0 i c | Concat(_, _, l,ll, r) -> if i < ll then unsafe_rindex offset i c l --- 598,603 ---- let rec unsafe_rindex offset i c = function ! | Sub(s, i0, _) -> ! rindex_string (offset - i0) s i0 (i0 + i) c | Concat(_, _, l,ll, r) -> if i < ll then unsafe_rindex offset i c l *************** *** 608,613 **** let rindex_from r i c = ! if i < 0 || i > length r then invalid_arg "Rope.rindex_from" ! else let j = unsafe_rindex 0 i c r in if j >= 0 then j else raise Not_found --- 607,611 ---- let rindex_from r i c = ! if i < 0 || i > length r then invalid_arg "Rope.rindex_from" else let j = unsafe_rindex 0 i c r in if j >= 0 then j else raise Not_found *************** *** 1166,1170 **** module Regexp = struct ! end --- 1164,1170 ---- module Regexp = struct ! (* FIXME: See also http://www.pps.jussieu.fr/~vouillon/ who is ! writing a DFA-based regular expression library. Would be nice to ! cooperate. *) end |
From: ChriS <chr...@us...> - 2007-12-25 03:06:28
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv11911/bench Modified Files: .depend.ocaml Makefile bm_ropes.ml bm_ropes.plot tinyRope.ml Log Message: - Corrected bug in [index] (thanks to Harmen for reporting it) and [rindex]. Index: bm_ropes.plot =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.plot,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** bm_ropes.plot 11 Aug 2007 11:14:03 -0000 1.4 --- bm_ropes.plot 25 Dec 2007 03:06:32 -0000 1.5 *************** *** 10,14 **** set key right set title "Min. unitary append time" ! plot [:] [1.7e-7:5.7e-7] \ "append.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ "append.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ --- 10,14 ---- set key right set title "Min. unitary append time" ! plot [:] [0.5e-7:5.7e-7] \ "append.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ "append.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/Makefile,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** Makefile 11 Aug 2007 11:14:03 -0000 1.3 --- Makefile 25 Dec 2007 03:06:32 -0000 1.4 *************** *** 1,5 **** UNSAFE=-noassert -unsafe LIBS=unix.cmxa ! INC=-I .. OCAMLOPT_FLAGS=-dtypes -inline 10 $(UNSAFE) $(INC) --- 1,7 ---- UNSAFE=-noassert -unsafe LIBS=unix.cmxa ! INC = -I .. -I ../_build ! ROPE_CMA = ../_build/rope.cma ! ROPE_CMXA = $(ROPE_CMA:.cma=.cmxa) OCAMLOPT_FLAGS=-dtypes -inline 10 $(UNSAFE) $(INC) *************** *** 10,17 **** byte: bench.byte ! bm_ropes.native: ../rope.cmxa tinyRope.cmx bm_ropes.ml $(OCAMLOPT) -o $@ $(OCAMLOPT_FLAGS) $(LIBS) $^ ! bm_ropes.byte: ../rope.cma tinyRope.cmo bm_ropes.ml $(OCAMLC) -o $@ $(OCAMLC_FLAGS) $(LIBS:.cmxa=.cma) $^ --- 12,19 ---- byte: bench.byte ! bm_ropes.native: $(ROPE_CMXA) tinyRope.cmx bm_ropes.ml $(OCAMLOPT) -o $@ $(OCAMLOPT_FLAGS) $(LIBS) $^ ! bm_ropes.byte: $(ROPE_CMA) tinyRope.cmo bm_ropes.ml $(OCAMLC) -o $@ $(OCAMLC_FLAGS) $(LIBS:.cmxa=.cma) $^ Index: .depend.ocaml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/.depend.ocaml,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** .depend.ocaml 11 Aug 2007 01:47:53 -0000 1.1 --- .depend.ocaml 25 Dec 2007 03:06:32 -0000 1.2 *************** *** 1,4 **** - bm_ropes.cmo: tinyRope.cmi - bm_ropes.cmx: tinyRope.cmx tinyRope.cmo: tinyRope.cmi tinyRope.cmx: tinyRope.cmi --- 1,2 ---- Index: tinyRope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/tinyRope.ml,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** tinyRope.ml 11 Aug 2007 11:14:03 -0000 1.3 --- tinyRope.ml 25 Dec 2007 03:06:32 -0000 1.4 *************** *** 86,90 **** (* let leaf_size = 128 *) (* let leaf_size = 64 *) ! let leaf_size = 32 (* =end *) --- 86,90 ---- (* let leaf_size = 128 *) (* let leaf_size = 64 *) ! (* let leaf_size = 32 *) (* =end *) Index: bm_ropes.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.ml,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** bm_ropes.ml 11 Aug 2007 11:14:03 -0000 1.4 --- bm_ropes.ml 25 Dec 2007 03:06:32 -0000 1.5 *************** *** 26,30 **** (* let n_ops = 10000 *) ! let max_nconcat = 5 (** how many concatenations of ropes (in the map) with lower length are accepted. [1] means: pick the laegest and complete appending --- 26,30 ---- (* let n_ops = 10000 *) ! let max_nconcat = 8 (** how many concatenations of ropes (in the map) with lower length are accepted. [1] means: pick the laegest and complete appending *************** *** 46,54 **** let datapoints = let basis = [1; 2; 3; 5; 17; 37; 53; 91; 201] in ! let basis = List.sort compare (list_init 15 (fun _ -> 1 + Random.int 200)) in let d = max_pox10 - min_pow10 in let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in ! Array.concat (List.map pow10_of basis @ [ [|max_int / 2 |] ] ! ) (* FIXME: for max_int, TinyRope segfaults!!! *) --- 46,53 ---- let datapoints = let basis = [1; 2; 3; 5; 17; 37; 53; 91; 201] in ! (* let basis = List.sort compare (list_init 15 (fun _ -> 1 + Random.int 200)) in *) let d = max_pox10 - min_pow10 in let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in ! Array.concat (List.map pow10_of basis (*@ [ [|max_int / 2 |] } *) ) (* FIXME: for max_int, TinyRope segfaults!!! *) *************** *** 242,246 **** IMap.empty datapoints in let times = List.map gather_times measl in ! let ch = open_out dst in Array.iter (fun size -> fprintf ch "%d" size; --- 241,245 ---- IMap.empty datapoints in let times = List.map gather_times measl in ! let ch = open_out (Filename.concat "bench" dst) in Array.iter (fun size -> fprintf ch "%d" size; |
From: ChriS <chr...@us...> - 2007-08-11 11:28:01
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv11240 Removed Files: rope_string.ml Log Message: Revoving rope_string.ml (an implementation using string leaves instead of substring leaves as the default one). Quick benchmark show it is of no interest. --- rope_string.ml DELETED --- |
From: ChriS <chr...@us...> - 2007-08-11 11:24:35
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv10420 Modified Files: rope.ml Log Message: Clarified the choice of value for [level_flatten]. Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** rope.ml 11 Aug 2007 11:16:59 -0000 1.7 --- rope.ml 11 Aug 2007 11:24:36 -0000 1.8 *************** *** 68,72 **** let level_flatten = 12 ! (** When balancing, flatten the rope at level [level_flatten]. *) let max_relocate_height = 35 --- 68,74 ---- let level_flatten = 12 ! (** When balancing, flatten the rope at level [level_flatten]. The ! sum of [min_length.(n)], [0 <= n <= level_flatten] must be of te ! same order as [max_flatten_length]. *) let max_relocate_height = 35 |
From: ChriS <chr...@us...> - 2007-08-11 11:17:02
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv6625 Modified Files: .cvsignore Makefile rope.ml Log Message: Changed the meaning of small_rope_length and max_flatten_length. The first indicates the size of leaves to be created of flattened for sure. The latter avoids to flatten too large ropes (and in particular of length to greater than Sys.max_string_length !). Index: .cvsignore =================================================================== RCS file: /cvsroot/ocaml-rope/rope/.cvsignore,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** .cvsignore 10 Aug 2007 19:29:26 -0000 1.1 --- .cvsignore 11 Aug 2007 11:16:59 -0000 1.2 *************** *** 5,6 **** --- 5,7 ---- *.cma *.cmxa + doc Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 *** rope.ml 11 Aug 2007 02:43:39 -0000 1.6 --- rope.ml 11 Aug 2007 11:16:59 -0000 1.7 *************** *** 53,62 **** type rope = t ! let max_flatten_length = 32 ! (** Ropes of length [<= max_flatten_length] may be flattened by ! [concat2]. [max_flatten_length] must be quite ! small, typically comparable to the size of a Concat node. *) ! let extract_sub_length = max_flatten_length / 2 (** When balancing, copy the substrings with this length or less (=> release the original string). *) --- 53,67 ---- type rope = t ! let small_rope_length = 32 ! (** Use this as leaf when creating fresh leaves. Also sub-ropes of ! length [<= small_rope_length] may be flattened by [concat2]. ! This value must be quite small, typically comparable to the size ! of a [Concat] node. *) ! let max_flatten_length = 1024 ! (** When deciding whther to flatten a rope, only those if length [<= ! max_flatten_length] will be. *) ! ! let extract_sub_length = small_rope_length / 2 (** When balancing, copy the substrings with this length or less (=> release the original string). *) *************** *** 65,71 **** (** When balancing, flatten the rope at level [level_flatten]. *) ! let small_rope_length = 32 ! (** Use this as leaf when creating fresh leaves. *) ! (* Fibonacci numbers $F_{n+2}$. By definition, a NON-EMPTY rope [r] --- 70,76 ---- (** When balancing, flatten the rope at level [level_flatten]. *) ! let max_relocate_height = 35 ! (** Only try to relocate rop leaves if the height of the tree is ! less or equal to this value. *) (* Fibonacci numbers $F_{n+2}$. By definition, a NON-EMPTY rope [r] *************** *** 331,336 **** [height(relocate_topright rope leaf _) = height rope] *) let rec relocate_topright rope leaf len_leaf = match rope with ! | Sub(_,_,_) -> failwith "relocate_right" | Concat(h, len, l,ll, r) -> let hr = height r + 1 in if hr < h then --- 336,342 ---- [height(relocate_topright rope leaf _) = height rope] *) let rec relocate_topright rope leaf len_leaf = match rope with ! | Sub(_,_,_) -> failwith "Rope.relocate_topright" | Concat(h, len, l,ll, r) -> + if h > max_relocate_height then failwith "Rope.relocate_topright"; let hr = height r + 1 in if hr < h then *************** *** 344,349 **** let rec relocate_topleft leaf len_leaf rope = match rope with ! | Sub(_,_,_) -> failwith "relocate_left" | Concat(h, len, l,ll, r) -> let hl = height l + 1 in if hl < h then --- 350,356 ---- let rec relocate_topleft leaf len_leaf rope = match rope with ! | Sub(_,_,_) -> failwith "Rope.relocate_topleft" | Concat(h, len, l,ll, r) -> + if h > max_relocate_height then failwith "Rope.relocate_topleft"; let hl = height l + 1 in if hl < h then *************** *** 374,378 **** | Sub(s1,i1,len1), Sub(s2,i2,len2) -> let len = len1 + len2 in ! if len <= max_flatten_length then let s = String.create len in String.unsafe_blit s1 i1 s 0 len1; --- 381,385 ---- | Sub(s1,i1,len1), Sub(s2,i2,len2) -> let len = len1 + len2 in ! if len <= small_rope_length then let s = String.create len in String.unsafe_blit s1 i1 s 0 len1; *************** *** 386,390 **** let len = len1 + len2 and lens = lens1 + len2 in ! if lens <= max_flatten_length then let s = String.create lens in String.unsafe_blit s1 i1 s 0 lens1; --- 393,397 ---- let len = len1 + len2 and lens = lens1 + len2 in ! if lens <= small_rope_length then let s = String.create lens in String.unsafe_blit s1 i1 s 0 lens1; *************** *** 401,405 **** (* if replacing [leaf1] will increase the height or if further concat will have an opportunity to add to a (small) leaf *) ! if h1 = h2plus1 || len2 < max_flatten_length then Concat(h1 + 1, len, rope1, len1, flatten rope2) else --- 408,413 ---- (* if replacing [leaf1] will increase the height or if further concat will have an opportunity to add to a (small) leaf *) ! if (h1 = h2plus1 && len2 <= max_flatten_length) ! || len2 < small_rope_length then Concat(h1 + 1, len, rope1, len1, flatten rope2) else *************** *** 413,417 **** let len = len1 + len2 and lens = len1 + lens2 in ! if lens <= max_flatten_length then let s = String.create lens in copy_to_substring s 0 rope1; --- 421,425 ---- let len = len1 + len2 and lens = len1 + lens2 in ! if lens <= small_rope_length then let s = String.create lens in copy_to_substring s 0 rope1; *************** *** 428,432 **** (* if replacing [leaf2] will increase the height or if further concat will have an opportunity to add to a (small) leaf *) ! if h1plus1 = h2 || len1 < max_flatten_length then Concat(h2 + 1, len, flatten rope1, len1, rope2) else --- 436,441 ---- (* if replacing [leaf2] will increase the height or if further concat will have an opportunity to add to a (small) leaf *) ! if (h1plus1 = h2 && len1 <= max_flatten_length) ! || len1 < small_rope_length then Concat(h2 + 1, len, flatten rope1, len1, rope2) else *************** *** 441,445 **** (* Small unbalanced ropes may happen if one concat left, then right, then left,.. *) ! if len <= max_flatten_length then let s = String.create len in copy_to_substring s 0 rope1; --- 450,454 ---- (* Small unbalanced ropes may happen if one concat left, then right, then left,.. *) ! if len <= small_rope_length then let s = String.create len in copy_to_substring s 0 rope1; *************** *** 448,454 **** else begin let rope1 = ! if len1 <= max_flatten_length then flatten rope1 else rope1 and rope2 = ! if len2 <= max_flatten_length then flatten rope2 else rope2 in let h = 1 + max (height rope1) (height rope2) in Concat(h, len1 + len2, rope1, len1, rope2) --- 457,463 ---- else begin let rope1 = ! if len1 <= small_rope_length then flatten rope1 else rope1 and rope2 = ! if len2 <= small_rope_length then flatten rope2 else rope2 in let h = 1 + max (height rope1) (height rope2) in Concat(h, len1 + len2, rope1, len1, rope2) *************** *** 498,501 **** --- 507,511 ---- let flatten_subrope rope i len = + assert(len <= Sys.max_string_length); let flat = String.create len in sub_to_substring flat 0 i len rope; *************** *** 537,544 **** if i < 0 || len < 0 || i > len_rope - len then invalid_arg "Rope.sub" else if len = 0 then empty ! else if len <= 1024 && len_rope >= 16384 then flatten_subrope rope i len ! (* The benefit of flattening such subropes (and constant) has been seen experimentally. It is not clear what the "exact" rule should be. *) else sub_rec i len rope --- 547,555 ---- if i < 0 || len < 0 || i > len_rope - len then invalid_arg "Rope.sub" else if len = 0 then empty ! else if len <= max_flatten_length && len_rope >= 32768 then ! (* The benefit of flattening such subropes (and constants) has been seen experimentally. It is not clear what the "exact" rule should be. *) + flatten_subrope rope i len else sub_rec i len rope *************** *** 830,834 **** we will cut into small chunks and add it directly to the forest. *) let create n = ! let n = if n < 1 then small_rope_length else n in { buf = String.create n; buf_len = n; --- 841,848 ---- we will cut into small chunks and add it directly to the forest. *) let create n = ! let n = ! if n < 1 then small_rope_length else ! if n > Sys.max_string_length then Sys.max_string_length ! else n in { buf = String.create n; buf_len = n; Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/Makefile,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** Makefile 11 Aug 2007 01:47:53 -0000 1.3 --- Makefile 11 Aug 2007 11:16:59 -0000 1.4 *************** *** 1,7 **** VERSION=0.2 SF_WEB = /home/groups/o/oc/ocaml-rope/htdocs ! SRC_WEB = NONE ! UNSAFE=-unsafe -noassert # speed gained by this is small OCAMLC_FLAGS= -dtypes -g $(UNSAFE) OCAMLOPT_FLAGS= -dtypes -inline 3 $(UNSAFE) --- 1,7 ---- VERSION=0.2 SF_WEB = /home/groups/o/oc/ocaml-rope/htdocs ! SRC_WEB = web ! #UNSAFE=-unsafe -noassert # speed gained by this is small OCAMLC_FLAGS= -dtypes -g $(UNSAFE) OCAMLOPT_FLAGS= -dtypes -inline 3 $(UNSAFE) *************** *** 25,31 **** unix.cmxa benchmark.cmxa $^ ! .PHONY: bench bench: rope.cmxa cd bench; $(MAKE) doc: $(wildcard *.mli) --- 25,33 ---- unix.cmxa benchmark.cmxa $^ ! .PHONY: bench bench.byte bench: rope.cmxa cd bench; $(MAKE) + bench.byte: rope.cma + cd bench; $(MAKE) byte doc: $(wildcard *.mli) |
From: ChriS <chr...@us...> - 2007-08-11 11:14:02
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv6232/bench Modified Files: Makefile bm_ropes.ml bm_ropes.plot tinyRope.ml Log Message: Improved the graphs layout. Added a random choice for the "pow10" tests. Index: bm_ropes.plot =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.plot,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** bm_ropes.plot 11 Aug 2007 09:54:04 -0000 1.3 --- bm_ropes.plot 11 Aug 2007 11:14:03 -0000 1.4 *************** *** 3,7 **** if (hardcopy) set terminal png size 650,800 set grid - set key left set logscale x --- 3,6 ---- *************** *** 9,19 **** set terminal wxt 1 enhanced raise set multiplot layout 2,1 downwards set title "Min. unitary append time" ! #plot [:] [1.5e-7:5e-7] ! plot \ "append.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ "append.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ "append-balanced.dat" using 1:2 with lines title "Tiny (balanced)", \ "append-balanced.dat" using 1:4 with lines title "FullFeatured (balanced)" set title "" set ylabel "depth (after appends)" --- 8,19 ---- set terminal wxt 1 enhanced raise set multiplot layout 2,1 downwards + set key right set title "Min. unitary append time" ! plot [:] [1.7e-7:5.7e-7] \ "append.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ "append.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ "append-balanced.dat" using 1:2 with lines title "Tiny (balanced)", \ "append-balanced.dat" using 1:4 with lines title "FullFeatured (balanced)" + set key bottom right set title "" set ylabel "depth (after appends)" *************** *** 23,31 **** --- 23,41 ---- "append-balanced.dat" using 1:3 with lines title "Tiny (balanced)", \ "append-balanced.dat" using 1:5 with lines title "FullFeatured (balanced)" + set ylabel "" + unset grid + set origin 0.1, 0.7 + set size 0.45,0.25 + plot [4e6:] \ + "append.dat" using 1:2 with lines notitle, \ + "append.dat" using 1:4 with lines lt 2 notitle, \ + "append-balanced.dat" using 1:4 with lines lt 4 notitle unset multiplot unset ylabel + set grid if (hardcopy) set output "get.png"; else set terminal wxt 2 raise set multiplot layout 2,1 downwards + set key top left set title "Min. unitary random get time" plot \ *************** *** 34,37 **** --- 44,48 ---- "get-balanced.dat" using 1:2 with lines title "Tiny (balanced)", \ "get-balanced.dat" using 1:4 with lines title "FullFeatured (balanced)" + set key bottom right set title "" set ylabel "depth" *************** *** 47,50 **** --- 58,62 ---- if (hardcopy) set output "sub.png"; else set terminal wxt 3 raise set multiplot layout 2,1 downwards + set key top left set title "Min. unitary random sub time" plot \ Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/Makefile,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** Makefile 11 Aug 2007 02:43:39 -0000 1.2 --- Makefile 11 Aug 2007 11:14:03 -0000 1.3 *************** *** 6,11 **** OCAMLC_FLAGS=-g $(INC) default: bench ! byte: bm_ropes.byte bm_ropes.native: ../rope.cmxa tinyRope.cmx bm_ropes.ml --- 6,12 ---- OCAMLC_FLAGS=-g $(INC) + .PHONY: default byte bench bench.byte default: bench ! byte: bench.byte bm_ropes.native: ../rope.cmxa tinyRope.cmx bm_ropes.ml *************** *** 18,21 **** --- 19,25 ---- ./$< && gnuplot -persist bm_ropes.plot + bench.byte: bm_ropes.byte + ./$< && gnuplot -persist bm_ropes.plot + OCAMLC ?= ocamlc Index: tinyRope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/tinyRope.ml,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** tinyRope.ml 11 Aug 2007 09:54:04 -0000 1.2 --- tinyRope.ml 11 Aug 2007 11:14:03 -0000 1.3 *************** *** 85,89 **** let leaf_size = 256 (* let leaf_size = 128 *) ! let leaf_size = 64 let leaf_size = 32 --- 85,89 ---- let leaf_size = 256 (* let leaf_size = 128 *) ! (* let leaf_size = 64 *) let leaf_size = 32 Index: bm_ropes.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.ml,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** bm_ropes.ml 11 Aug 2007 09:54:04 -0000 1.3 --- bm_ropes.ml 11 Aug 2007 11:14:03 -0000 1.4 *************** *** 20,23 **** --- 20,24 ---- open Printf + let () = Random.self_init() let nsamples = 30 *************** *** 39,47 **** let rec pow n = function 0 -> 1 | i -> n * pow n (i - 1) let datapoints = let d = max_pox10 - min_pow10 in let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in ! Array.concat (List.map pow10_of [1; 2; 3; 5; 17; 37; 51; 91; 201] ! @ [ [|max_int / 2 |] ] ) (* FIXME: for max_int, TinyRope segfaults!!! *) --- 40,53 ---- let rec pow n = function 0 -> 1 | i -> n * pow n (i - 1) + let list_init n f = + let rec make acc n = if n < 0 then acc else make (f n :: acc) (n - 1) in + make [] (n-1) + let datapoints = + let basis = [1; 2; 3; 5; 17; 37; 53; 91; 201] in + let basis = List.sort compare (list_init 15 (fun _ -> 1 + Random.int 200)) in let d = max_pox10 - min_pow10 in let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in ! Array.concat (List.map pow10_of basis @ [ [|max_int / 2 |] ] ) (* FIXME: for max_int, TinyRope segfaults!!! *) *************** *** 61,66 **** d - let () = Random.self_init() - (* just for laughs *) let basic_loop_overhead = --- 67,70 ---- |
From: ChriS <chr...@us...> - 2007-08-11 09:54:03
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv7076/bench Modified Files: bm_ropes.ml bm_ropes.plot tinyRope.ml Log Message: Changed the depth plotted for sub (average depth after sub and not before). Index: bm_ropes.plot =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.plot,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** bm_ropes.plot 11 Aug 2007 02:43:39 -0000 1.2 --- bm_ropes.plot 11 Aug 2007 09:54:04 -0000 1.3 *************** *** 54,58 **** "sub.dat" using 1:8 with lines title "FullFeatured (balanced)" set title "" ! set ylabel "depth" plot \ "sub.dat" using 1:3 with linespoints title "Tiny (unbalanced)", \ --- 54,58 ---- "sub.dat" using 1:8 with lines title "FullFeatured (balanced)" set title "" ! set ylabel "depth (average after sub)" plot \ "sub.dat" using 1:3 with linespoints title "Tiny (unbalanced)", \ Index: tinyRope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/tinyRope.ml,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** tinyRope.ml 11 Aug 2007 01:47:53 -0000 1.1 --- tinyRope.ml 11 Aug 2007 09:54:04 -0000 1.2 *************** *** 85,89 **** let leaf_size = 256 (* let leaf_size = 128 *) ! (* let leaf_size = 64 *) let leaf_size = 32 --- 85,89 ---- let leaf_size = 256 (* let leaf_size = 128 *) ! let leaf_size = 64 let leaf_size = 32 Index: bm_ropes.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.ml,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** bm_ropes.ml 11 Aug 2007 02:43:39 -0000 1.2 --- bm_ropes.ml 11 Aug 2007 09:54:04 -0000 1.3 *************** *** 91,96 **** print_string msg; let samples = ! Array.init nsamples (fun i -> printf "%2d/%4d\r%!" (i + 1) nsamples; f x) in ! printf " \r%!"; let min_sample (tmin,_) (t,d) = (min tmin t, d) in Array.fold_left min_sample (max_float, max_int) samples --- 91,96 ---- print_string msg; let samples = ! Array.init nsamples (fun i -> printf "\r%2d/%4d%!" (i + 1) nsamples; f x) in ! printf "\r \r%!"; let min_sample (tmin,_) (t,d) = (min tmin t, d) in Array.fold_left min_sample (max_float, max_int) samples *************** *** 181,189 **** let r = make_rope size in let t0 = Unix.gettimeofday () in for i = 0 to n_ops - 1 do ! ignore(M.sub r 0 (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in ! (dt -. random_loop_overhead) /. float n_ops, M.height r let measure_sub_time size = --- 181,191 ---- let r = make_rope size in let t0 = Unix.gettimeofday () in + let h = ref 0 in for i = 0 to n_ops - 1 do ! h := !h + M.height(M.sub r 0 (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in ! (dt -. random_loop_overhead) /. float n_ops, ! truncate(0.5 +. float !h /. float n_ops) (* round *) let measure_sub_time size = |
From: ChriS <chr...@us...> - 2007-08-11 02:43:37
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv6263/bench Modified Files: Makefile bm_ropes.ml bm_ropes.plot Added Files: .cvsignore Log Message: Added some explanation about the flattening rule of [sub]. --- NEW FILE: .cvsignore --- *.annot *.cmi *.cmo *.cmx *.cma *.cmxa *.byte *.native *.dat *.png Index: bm_ropes.plot =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.plot,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** bm_ropes.plot 11 Aug 2007 01:47:53 -0000 1.1 --- bm_ropes.plot 11 Aug 2007 02:43:39 -0000 1.2 *************** *** 1,11 **** ! set terminal png size 650,800 set grid set key left set logscale x ! set output "append.png" set multiplot layout 2,1 downwards set title "Min. unitary append time" plot \ "append.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ --- 1,14 ---- + hardcopy = 1 ! if (hardcopy) set terminal png size 650,800 set grid set key left set logscale x ! if (hardcopy) set output "append.png"; else \ ! set terminal wxt 1 enhanced raise set multiplot layout 2,1 downwards set title "Min. unitary append time" + #plot [:] [1.5e-7:5e-7] plot \ "append.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ *************** *** 23,27 **** unset ylabel ! set output "get.png" set multiplot layout 2,1 downwards set title "Min. unitary random get time" --- 26,30 ---- unset ylabel ! if (hardcopy) set output "get.png"; else set terminal wxt 2 raise set multiplot layout 2,1 downwards set title "Min. unitary random get time" *************** *** 42,46 **** unset ylabel ! set output "sub.png" set multiplot layout 2,1 downwards set title "Min. unitary random sub time" --- 45,49 ---- unset ylabel ! if (hardcopy) set output "sub.png"; else set terminal wxt 3 raise set multiplot layout 2,1 downwards set title "Min. unitary random sub time" Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/Makefile,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** Makefile 11 Aug 2007 01:47:53 -0000 1.1 --- Makefile 11 Aug 2007 02:43:39 -0000 1.2 *************** *** 16,20 **** bench: bm_ropes.native ! ./$< && gnuplot bm_ropes.plot --- 16,20 ---- bench: bm_ropes.native ! ./$< && gnuplot -persist bm_ropes.plot Index: bm_ropes.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/bench/bm_ropes.ml,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** bm_ropes.ml 11 Aug 2007 01:47:53 -0000 1.1 --- bm_ropes.ml 11 Aug 2007 02:43:39 -0000 1.2 *************** *** 43,47 **** let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in Array.concat (List.map pow10_of [1; 2; 3; 5; 17; 37; 51; 91; 201] ! (* @ [ [|max_int / 2 |] ] *) ) (* FIXME: for max_int, TinyRope segfaults!!! *) --- 43,47 ---- let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in Array.concat (List.map pow10_of [1; 2; 3; 5; 17; 37; 51; 91; 201] ! @ [ [|max_int / 2 |] ] ) (* FIXME: for max_int, TinyRope segfaults!!! *) *************** *** 50,54 **** Array.concat [ (Array.init 20 (fun _ -> 10000 + Random.int 10_000_000)); ! (Array.init 20 (fun _ -> 10_000_000 + Random.int 50_000_000)) ] --- 50,54 ---- Array.concat [ (Array.init 20 (fun _ -> 10000 + Random.int 10_000_000)); ! (Array.init 20 (fun _ -> 10_000_000 + Random.int 50_000_000)); ] |
From: ChriS <chr...@us...> - 2007-08-11 02:43:37
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv6263 Modified Files: rope.ml Log Message: Added some explanation about the flattening rule of [sub]. Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 *** rope.ml 11 Aug 2007 01:47:53 -0000 1.5 --- rope.ml 11 Aug 2007 02:43:39 -0000 1.6 *************** *** 538,541 **** --- 538,544 ---- else if len = 0 then empty else if len <= 1024 && len_rope >= 16384 then flatten_subrope rope i len + (* The benefit of flattening such subropes (and constant) has been + seen experimentally. It is not clear what the "exact" rule + should be. *) else sub_rec i len rope |
From: ChriS <chr...@us...> - 2007-08-11 01:47:58
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv17373/bench Added Files: .depend.ocaml Makefile bm_ropes.ml bm_ropes.plot tinyRope.ml tinyRope.mli Log Message: Added benchmark suite developed by Mauricio Fernandez and myself. --- NEW FILE: tinyRope.mli --- (* Rope: a simple implementation of ropes as described in Boehm, H., Atkinson, R., and Plass, M. 1995. Ropes: an alternative to strings. Softw. Pract. Exper. 25, 12 (Dec. 1995), 1315-1330. Motivated by Luca de Alfaro's extensible array implementation Vec. Copyright (C) 2007 Mauricio Fernandez <mf...@ac...> http://eigenclass.org This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version, with the following special exception: You may link, statically or dynamically, a "work that uses the Library" with a publicly distributed version of the Library to produce an executable file containing portions of the Library, and distribute that executable file under terms of your choice, without any of the additional requirements listed in clause 6 of the GNU Library General Public License. By "a publicly distributed version of the Library", we mean either the unmodified Library as distributed by the author, or a modified version of the Library that is distributed under the conditions defined in clause 2 of the GNU Library General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU Library General Public License. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. The GNU Library General Public License is available at http://www.gnu.org/copyleft/lgpl.html; to obtain it, you can also write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *) (** Heavyweight strings ("ropes") This module implements ropes as described in Boehm, H., Atkinson, R., and Plass, M. 1995. Ropes: an alternative to strings. Softw. Pract. Exper. 25, 12 (Dec. 1995), 1315-1330. Ropes are an alternative to strings which support efficient operations: - determining the length of a rope in constant time - appending or prepending a small rope to an arbitrarily large one in amortized constant time - concat, substring, insert, remove operations in amortized logarithmic time - access to and modification of ropes in logarithmic time {8 Functional nature and persistence} All operations are non-destructive: the original rope is never modified. When a new rope is returned as the result of an operation, it will share as much data as possible with its "parent". For instance, if a rope of length [n] undergoes [m] operations (assume [n >> m]) like set, append or prepend, the modified rope will only require [O(m)] space in addition to that taken by the original one. However, Rope is an amortized data structure, and its use in a persistent setting can easily degrade its amortized time bounds. It is thus mainly intended to be used ephemerally. In some cases, it is possible to use Rope persistently with the same amortized bounds by explicitly rebalancing ropes to be reused using [balance]. Special care must be taken to avoid calling [balance] too frequently; in the limit, calling [balance] after each modification would defeat the purpose of amortization. @author Mauricio Fernandez *) type t (** The type of the ropes. *) exception Out_of_bounds (** Raised when an operation violates the bounds of the rope. *) val max_length : int (** Maximum length of the rope. *) (** {6 Creation and conversions} *) val empty : t (** The empty rope. *) val of_string : string -> t (** [of_string s] returns a rope corresponding to the string [s]. Operates in [O(n)] time. *) val to_string : t -> string (** [to_string r] returns the string corresponding to the rope [r]. *) val make : int -> char -> t (** [make i c] returns a rope of length [i] consisting of [c] chars; it is similar to String.make *) (** {6 Properties } *) val is_empty : t -> bool (** Returns whether the rope is empty or not. *) val length : t -> int (** Returns the length of the rope ([O(1)]). *) val height : t -> int (** Returns the height (depth) of the rope. *) val balance : t -> t (** [balance r] returns a balanced copy of the [r] rope. Note that ropes are automatically rebalanced when their height exceeds a given threshold, but [balance] allows to invoke that operation explicity. *) (** {6 Operations } *) val concat : t -> t -> t (** [concat r u] concatenates the [r] and [u] ropes. In general, it operates in [O(log(min n1 n2))] amortized time. Small ropes are treated specially and can be appended/prepended in amortized [O(1)] time. *) val append_char : char -> t -> t (** [append_char c r] returns a new rope with the [c] character at the end in amortized [O(1)] time. *) val prepend_char : char -> t -> t (** [prepend_char c r] returns a new rope with the [c] character at the beginning in amortized [O(1)] time. *) val get : int -> t -> char (** [get n r] returns the (n+1)th character from the rope [r]; i.e. [get 0 r] returns the first character. Operates in worst-case [O(log size)] time. Raises Out_of_bounds if a character out of bounds is requested. *) val set : int -> char -> t -> t (** [set n c r] returns a copy of the [r] rope where the (n+1)th character (see also [get]) has been set to [c]. Operates in worst-case [O(log size)] time. *) val sub : int -> int -> t -> t (** [sub m n r] returns a sub-rope of [r] containing all characters whose indexes range from [m] to [m + n - 1] (included). Raises Out_of_bounds in the same cases as String.sub. Operates in worst-case [O(log size)] time. *) val insert : int -> t -> t -> t (** [insert n r u] returns a copy of the [u] rope where [r] has been inserted between the characters with index [n] and [n + 1] in the original string. The length of the new rope is [length u + length r]. Operates in amortized [O(log(size r) + log(size u))] time. *) val remove : int -> int -> t -> t (** [remove m n r] returns the rope resulting from deleting the characters with indexes ranging from [m] to [m + n - 1] (included) from the original rope [r]. The length of the new rope is [length r - n]. Operates in amortized [O(log(size r))] time. *) (** {6 Iteration} *) val iter : (char -> unit) -> t -> unit (** [iter f r] applies [f] to all the characters in the [r] rope, in order. *) val iteri : (int -> char -> unit) -> t -> unit (** Operates like iter, but also passes the index of the character to the given function. *) val rangeiter : (char -> unit) -> int -> int -> t -> unit (** [rangeiter f m n r] applies [f] to all the characters whose indices [k] satisfy [m] <= [k] < [m + n]. It is thus equivalent to [iter f (sub m n r)], but does not create an intermediary rope. [rangeiter] operates in worst-case [O(n + log m)] time, which improves on the [O(n log m)] bound from an explicit loop using [get]. Raises Out_of_bounds in the same cases as [sub]. *) val fold : ('a -> char -> 'a ) -> 'a -> t -> 'a (** [Rope.fold f a r] computes [ f (... (f (f a r0) r1)...) rN-1 ] where [rn = Rope.get n r ] and [N = length r]. *) (**/**) val print : t -> unit val getn : int -> t -> int --- NEW FILE: Makefile --- UNSAFE=-noassert -unsafe LIBS=unix.cmxa INC=-I .. OCAMLOPT_FLAGS=-dtypes -inline 10 $(UNSAFE) $(INC) OCAMLC_FLAGS=-g $(INC) default: bench byte: bm_ropes.byte bm_ropes.native: ../rope.cmxa tinyRope.cmx bm_ropes.ml $(OCAMLOPT) -o $@ $(OCAMLOPT_FLAGS) $(LIBS) $^ bm_ropes.byte: ../rope.cma tinyRope.cmo bm_ropes.ml $(OCAMLC) -o $@ $(OCAMLC_FLAGS) $(LIBS:.cmxa=.cma) $^ bench: bm_ropes.native ./$< && gnuplot bm_ropes.plot OCAMLC ?= ocamlc OCAMLOPT ?= ocamlopt OCAMLDEP ?= ocamldep OCAMLDOC ?= ocamldoc OCAMLFIND ?= ocamlfind OCAMLTAGS ?= ocamltags # Caml general dependencies .SUFFIXES: .cmo .cmi .cmx .ml .mli %.cmi: %.mli $(OCAMLC) $(OCAMLC_FLAGS) -c $< %.cmo: %.ml $(OCAMLC) $(PP) $(OCAMLC_FLAGS) -c $< %.cma: %.cmo $(OCAMLC) $(PP) -a -o $@ $(OCAMLC_FLAGS) $< %.cmx: %.ml $(OCAMLOPT) $(PP) $(OCAMLOPT_FLAGS) -c $< %.cmxa: %.cmx $(OCAMLOPT) $(PP) -a -o $@ $(OCAMLOPT_FLAGS) $< %.byte: %.ml $(OCAMLC) -o $@ $(PP) $(OCAMLC_FLAGS) $< %.native: %.ml $(OCAMLOPT) -o $@ $(PP) $(OCAMLOPT_FLAGS) $< .depend.ocaml: $(wildcard *.ml) $(wildcard *.mli) $(OCAMLDEP) $(PP) $(SYNTAX_OPTS) $^ > $@ include .depend.ocaml .PHONY: clean clean:: $(RM) -f *.cm{i,o,x,a,xa} *.annot *.o *.a *~ $(RM) *.dat *.png find . -type f -perm -u=x -exec rm -f {} \; --- NEW FILE: bm_ropes.plot --- set terminal png size 650,800 set grid set key left set logscale x set output "append.png" set multiplot layout 2,1 downwards set title "Min. unitary append time" plot \ "append.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ "append.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ "append-balanced.dat" using 1:2 with lines title "Tiny (balanced)", \ "append-balanced.dat" using 1:4 with lines title "FullFeatured (balanced)" set title "" set ylabel "depth (after appends)" plot \ "append.dat" using 1:3 with linespoints title "Tiny (unbalanced)", \ "append.dat" using 1:5 with linespoints title "FullFeatured (unbalanced)", \ "append-balanced.dat" using 1:3 with lines title "Tiny (balanced)", \ "append-balanced.dat" using 1:5 with lines title "FullFeatured (balanced)" unset multiplot unset ylabel set output "get.png" set multiplot layout 2,1 downwards set title "Min. unitary random get time" plot \ "get.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ "get.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ "get-balanced.dat" using 1:2 with lines title "Tiny (balanced)", \ "get-balanced.dat" using 1:4 with lines title "FullFeatured (balanced)" set title "" set ylabel "depth" plot \ "get.dat" using 1:3 with linespoints title "Tiny (unbalanced)", \ "get.dat" using 1:5 with linespoints title "FullFeatured (unbalanced)", \ "get-balanced.dat" using 1:3 with lines title "Tiny (balanced)", \ "get-balanced.dat" using 1:5 with lines title "FullFeatured (balanced)", \ log(x / 32.)/log(2.) with lines title "Optimal (|leaf|=32)" unset multiplot unset ylabel set output "sub.png" set multiplot layout 2,1 downwards set title "Min. unitary random sub time" plot \ "sub.dat" using 1:2 with linespoints title "Tiny (unbalanced)", \ "sub.dat" using 1:4 with linespoints title "FullFeatured (unbalanced)", \ "sub.dat" using 1:6 with lines title "Tiny (balanced)", \ "sub.dat" using 1:8 with lines title "FullFeatured (balanced)" set title "" set ylabel "depth" plot \ "sub.dat" using 1:3 with linespoints title "Tiny (unbalanced)", \ "sub.dat" using 1:5 with linespoints title "FullFeatured (unbalanced)", \ "sub.dat" using 1:7 with lines title "Tiny (balanced)", \ "sub.dat" using 1:9 with lines title "FullFeatured (balanced)" unset multiplot unset logscale x # Local Variables: # mode: gnuplot # End: --- NEW FILE: bm_ropes.ml --- (* File: bm_ropes.ml Copyright (C) 2007 Christophe Troestler <Chr...@um...> WWW: http://math.umh.ac.be/an/software/ Mauricio Fernandez <mf...@ac...> http://eigenclass.org This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2.1 or later as published by the Free Software Foundation, with the special exception on linking described in the file LICENSE. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the file LICENSE for more details. *) open Printf let nsamples = 30 let n_ops = 1000 (* let n_ops = 10000 *) let max_nconcat = 5 (** how many concatenations of ropes (in the map) with lower length are accepted. [1] means: pick the laegest and complete appending chars. *) let prepend_size = 128 (** if [size land prepend_size = 0] prepend chars instead of appending. Set to [max_int]: always append (never prepend). Set to [0]: always preprend. *) let min_pow10 = 2 let max_pox10 = 7 let rec pow n = function 0 -> 1 | i -> n * pow n (i - 1) let datapoints = let d = max_pox10 - min_pow10 in let pow10_of j = Array.init d (fun i -> j * pow 10 (i + min_pow10)) in Array.concat (List.map pow10_of [1; 2; 3; 5; 17; 37; 51; 91; 201] (* @ [ [|max_int / 2 |] ] *) ) (* FIXME: for max_int, TinyRope segfaults!!! *) let datapoints2 = Array.concat [ (Array.init 20 (fun _ -> 10000 + Random.int 10_000_000)); (Array.init 20 (fun _ -> 10_000_000 + Random.int 50_000_000)) ] (* ---------------------------------------------------------------------- *) let datapoints_ordered = let d = Array.copy datapoints in Array.sort compare d; d let () = Random.self_init() (* just for laughs *) let basic_loop_overhead = let t1 = Unix.gettimeofday () in for j = 0 to 100 do for i = 0 to n_ops do ignore () done done; (Unix.gettimeofday () -. t1) /. 100.0 let random_loop_overhead = let t1 = Unix.gettimeofday () in for j = 0 to 100 do for i = 0 to n_ops do ignore (Random.int 10000) done; done; (Unix.gettimeofday () -. t1) /. 100.0 let () = printf "Random loop overhead: %12.10f\n" random_loop_overhead; printf "Basic loop overhead: %12.10f\n" basic_loop_overhead let time ~msg f x = let t0 = Sys.time () in let r = f x in printf "%s needed %8.5fs\n%!" msg (Sys.time () -. t0); r let sample msg f x = print_string msg; let samples = Array.init nsamples (fun i -> printf "%2d/%4d\r%!" (i + 1) nsamples; f x) in printf " \r%!"; let min_sample (tmin,_) (t,d) = (min tmin t, d) in Array.fold_left min_sample (max_float, max_int) samples (* let sum_sample (tsum, _) (t,d) = (tsum +. t, d) in let t, d = Array.fold_left sum_sample (0.0, 0) samples in t /. float_of_int nsamples, d *) module IMap = Map.Make(struct type t = int let compare = compare end) module Benchmark(M : sig type t val name : string val balanced : bool val empty : t val append : char -> t -> t val prepend : char -> t -> t val concat : t -> t -> t val length : t -> int val height : t -> int val balance : t -> t val get : t -> int -> char val sub : t -> int -> int -> t end) = struct (** [make_rope size] returns a rope of length [size]. We concatenate small ropes as it is more reprensentative than only appending repeatedly chars. *) let make_rope = let rope_tbl = ref IMap.empty in let rec add_chars r c size = if size <= 0 then r else let op = if size land prepend_size = 0 then M.prepend else M.append in add_chars (op c r) c (size - 1) in let rec build nconcat r size = let largest = IMap.fold (fun _ v s -> let len = M.length v in if len > M.length s && len <= size then v else s ) !rope_tbl M.empty in if M.length largest = 0 || nconcat > max_nconcat then (* no piece to add to [r] *) add_chars r 'x' (size - M.length largest) else let r' = if Random.bool() then M.concat r largest else M.concat largest r in build (nconcat + 1) r' (size - M.length largest) in fun size -> let r = build 0 M.empty size in rope_tbl := IMap.add size r !rope_tbl; if M.balanced then M.balance r else r ;; let append_time size = let v = ref (make_rope size) in let t0 = Unix.gettimeofday () in for i = 0 to n_ops - 1 do v := M.append 'z' !v; (* ignore (append_f I !v); *) done; let dt = (Unix.gettimeofday () -. t0) in (dt -. basic_loop_overhead) /. (float_of_int n_ops), M.height !v let measure_append_time size = let msg = sprintf "Append time for %s of size %d\n%!" M.name size in sample msg append_time size let random_get_time size = let r = make_rope size in (* Gc.full_major (); *) let t0 = Unix.gettimeofday () in (* let sum = ref 0 in *) for i = 0 to n_ops - 1 do ignore(M.get r (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in (dt -. random_loop_overhead) /. float n_ops, M.height r (* float !sum /. float n_ops, M.height r *) let measure_random_get_time size = let msg = sprintf "Random get time for %s of size %d\n%!" M.name size in sample msg random_get_time size let sub_time size = let r = make_rope size in let t0 = Unix.gettimeofday () in for i = 0 to n_ops - 1 do ignore(M.sub r 0 (Random.int size)); done; let dt = (Unix.gettimeofday () -. t0) in (dt -. random_loop_overhead) /. float n_ops, M.height r let measure_sub_time size = let msg = sprintf "Sub time for %s of size %d\n%!" M.name size in sample msg sub_time size end module TinyBM = struct type t = TinyRope.t let name = "TinyRope" let empty = TinyRope.empty let append = TinyRope.append_char let prepend = TinyRope.prepend_char let concat = TinyRope.concat let length = TinyRope.length let height = TinyRope.height let balance = TinyRope.balance let get r i = TinyRope.get i r let sub r start len = TinyRope.sub start len r end module FullBM = struct type t = Rope.t let name = "Rope" let empty = Rope.empty let append c r = Rope.concat2 r (Rope.of_char c) let prepend c r = Rope.concat2 (Rope.of_char c) r let concat = Rope.concat2 let length = Rope.length let height = Rope.height let balance = Rope.balance let get = Rope.get let sub = Rope.sub end module BalancedFullBM = Benchmark(struct include FullBM let balanced = true end) module UnbalancedFullBM = Benchmark(struct include FullBM let balanced = false end) module BalancedTinyBM = Benchmark(struct include TinyBM let balanced = true end) module UnbalancedTinyBM = Benchmark(struct include TinyBM let balanced = false end) let benchmark dst measl = let gather_times f = Array.fold_left (fun bm size -> IMap.add size (f size) bm) IMap.empty datapoints in let times = List.map gather_times measl in let ch = open_out dst in Array.iter (fun size -> fprintf ch "%d" size; List.iter (fun tbl -> let t, sz = IMap.find size tbl in fprintf ch "\t%12.10e\t%i" t sz ) times; fprintf ch "\n" ) datapoints_ordered; close_out ch let () = benchmark "append.dat" [UnbalancedTinyBM.measure_append_time; UnbalancedFullBM.measure_append_time ]; Gc.full_major (); benchmark "get.dat" [UnbalancedTinyBM.measure_random_get_time; UnbalancedFullBM.measure_random_get_time ]; Gc.full_major (); benchmark "append-balanced.dat" [BalancedTinyBM.measure_append_time; BalancedFullBM.measure_append_time]; Gc.full_major (); benchmark "get-balanced.dat" [BalancedTinyBM.measure_random_get_time; BalancedFullBM.measure_random_get_time]; Gc.full_major (); benchmark "sub.dat" [UnbalancedTinyBM.measure_sub_time; UnbalancedFullBM.measure_sub_time; BalancedTinyBM.measure_sub_time; BalancedFullBM.measure_sub_time ]; () --- NEW FILE: .depend.ocaml --- bm_ropes.cmo: tinyRope.cmi bm_ropes.cmx: tinyRope.cmx tinyRope.cmo: tinyRope.cmi tinyRope.cmx: tinyRope.cmi --- NEW FILE: tinyRope.ml --- (* Rope: an implementation of the data structure described in Boehm, H., Atkinson, R., and Plass, M. 1995. Ropes: an alternative to strings. Softw. Pract. Exper. 25, 12 (Dec. 1995), 1315-1330. Motivated by Luca de Alfaro's extensible array implementation Vec. Copyright (C) 2007 Mauricio Fernandez <mf...@ac...> http://eigenclass.org This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version, with the following special exception: You may link, statically or dynamically, a "work that uses the Library" with a publicly distributed version of the Library to produce an executable file containing portions of the Library, and distribute that executable file under terms of your choice, without any of the additional requirements listed in clause 6 of the GNU Library General Public License. By "a publicly distributed version of the Library", we mean either the unmodified Library as distributed by the author, or a modified version of the Library that is distributed under the conditions defined in clause 2 of the GNU Library General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU Library General Public License. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. The GNU Library General Public License is available at http://www.gnu.org/copyleft/lgpl.html; to obtain it, you can also write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *) (* =begin ignore *) type t = Empty (* left, left size, right, right size, height *) | Concat of t * int * t * int * int | Leaf of string let height = function Empty | Leaf _ -> 0 | Concat(_,_,_,_,h) -> h (* For debugging and judging balancing *) let print = let rec print prefix = function | Empty -> print_string "\n" | Leaf s -> print_string prefix; print_string s; print_string "\n" | Concat(l,_, r,_, _) -> let prefixl = prefix ^ if height l = 0 then "/" else " " in let prefixr = prefix ^ if height r = 0 then "\\" else " " in print prefixl l; print prefixr r; in print "" type forest_element = { mutable c : t; mutable len : int } let str_append = (^) let empty_str = "" let string_of_string_list l = String.concat "" l module STRING = String (* 48 limits max rope size to 220GB on 64 bit, * ~ 700MB on 32bit (length fields overflow after that) *) let max_height = 48 (* actual size will be that plus 1 word header; * the code assumes it's an even num. * 256 gives up to a 50% overhead in the worst case (all leaf nodes near * half-filled *) let leaf_size = 256 (* let leaf_size = 128 *) (* let leaf_size = 64 *) let leaf_size = 32 (* =end *) (* =begin code *) exception Out_of_bounds let empty = Empty (* by construction, there cannot be Empty or Leaf "" leaves *) let is_empty = function Empty -> true | _ -> false let rec length = function Empty -> 0 | Leaf s -> STRING.length s | Concat(_,cl,_,cr,_) -> cl + cr let make_concat l r = let hl = height l and hr = height r in let cl = length l and cr = length r in Concat(l, cl, r, cr, if hl >= hr then hl + 1 else hr + 1) let min_len = let fib_tbl = Array.make max_height 0 in let rec fib n = match fib_tbl.(n) with 0 -> let last = fib (n - 1) and prev = fib (n - 2) in let r = last + prev in let r = if r > last then r else last in (* check overflow *) fib_tbl.(n) <- r; r | n -> n in fib_tbl.(0) <- leaf_size + 1; fib_tbl.(1) <- 3 * leaf_size / 2 + 1; Array.init max_height (fun i -> if i = 0 then 1 else fib (i - 1)) let max_length = min_len.(Array.length min_len - 1) let concat_fast l r = match l with Empty -> r | Leaf _ | Concat(_,_,_,_,_) -> match r with Empty -> l | Leaf _ | Concat(_,_,_,_,_) -> make_concat l r (* based on Hans-J. Boehm's *) let add_forest forest rope len = let i = ref 0 in let sum = ref empty in while len > min_len.(!i+1) do if forest.(!i).c <> Empty then begin sum := concat_fast forest.(!i).c !sum; forest.(!i).c <- Empty end; incr i done; sum := concat_fast !sum rope; let sum_len = ref (length !sum) in while !sum_len >= min_len.(!i) do if forest.(!i).c <> Empty then begin sum := concat_fast forest.(!i).c !sum; sum_len := !sum_len + forest.(!i).len; forest.(!i).c <- Empty; end; incr i done; decr i; forest.(!i).c <- !sum; forest.(!i).len <- !sum_len let concat_forest forest = Array.fold_left (fun s x -> concat_fast x.c s) Empty forest let rec balance_insert rope len forest = match rope with Empty -> () | Leaf _ -> add_forest forest rope len | Concat(l,cl,r,cr,h) when h >= max_height || len < min_len.(h) -> balance_insert l cl forest; balance_insert r cr forest | x -> add_forest forest x len (* function or balanced *) let balance r = match r with Empty -> Empty | Leaf _ -> r | _ -> let forest = Array.init max_height (fun _ -> {c = Empty; len = 0}) in balance_insert r (length r) forest; concat_forest forest let bal_if_needed l r = let r = make_concat l r in if height r < max_height then r else balance r let concat_str l = function Empty | Concat(_,_,_,_,_) -> invalid_arg "concat_str" | Leaf rs as r -> let lenr = STRING.length rs in match l with | Empty -> r | Leaf ls -> let slen = lenr + STRING.length ls in if slen <= leaf_size then Leaf (str_append ls rs) else make_concat l r (* height = 1 *) | Concat(ll, cll, Leaf lrs, clr, h) -> let slen = clr + lenr in if clr + lenr <= leaf_size then Concat(ll, cll, Leaf (str_append lrs rs), slen, h) else bal_if_needed l r | _ -> bal_if_needed l r let append_char c r = concat_str r (Leaf (STRING.make 1 c)) let concat l = function Empty -> l | Leaf _ as r -> concat_str l r | Concat(Leaf rls,rlc,rr,rc,h) as r -> (match l with Empty -> r | Concat(_,_,_,_,_) -> bal_if_needed l r | Leaf ls -> let slen = rlc + STRING.length ls in if slen <= leaf_size then Concat(Leaf(str_append ls rls), slen, rr, rc, h) else bal_if_needed l r) | r -> (match l with Empty -> r | _ -> bal_if_needed l r) let prepend_char c r = concat (Leaf (STRING.make 1 c)) r let rec get i = function Empty -> raise Out_of_bounds | Leaf s -> if i >= 0 && i < STRING.length s then STRING.unsafe_get s i else raise Out_of_bounds | Concat (l, cl, r, cr, _) -> if i < cl then get i l else get (i - cl) r let rec getn i = function Empty -> raise Out_of_bounds | Leaf s -> 0 | Concat (l, cl, r, cr, _) -> if i < cl then 1 + getn i l else 1 + getn (i - cl) r let rec set i v = function Empty -> raise Out_of_bounds | Leaf s -> if i >= 0 && i < STRING.length s then let s = STRING.copy s in STRING.unsafe_set s i v; Leaf s else raise Out_of_bounds | Concat(l, cl, r, cr, _) -> if i < cl then concat (set i v l) r else concat l (set (i - cl) v r) let of_string = function s when STRING.length s = 0 -> Empty | s -> let min (x:int) (y:int) = if x <= y then x else y in let rec loop r s len i = if i < len then (* len - i > 0, thus Leaf "" can't happen *) loop (concat r (Leaf (STRING.sub s i (min (len - i) leaf_size)))) s len (i + leaf_size) else r in loop Empty s (STRING.length s) 0 let rec make len c = let rec concatloop len i r = if i <= len then concatloop len (i * 2) (concat r r) else r in if len = 0 then Empty else if len <= leaf_size then Leaf (STRING.make len c) else let rope = concatloop len 2 (of_string (STRING.make 1 c)) in concat rope (make (len - length rope) c) let rec sub start len = function Empty -> if start <> 0 || len <> 0 then raise Out_of_bounds else Empty | Leaf s -> if len > 0 then (* Leaf "" cannot happen *) (try Leaf (STRING.sub s start len) with _ -> raise Out_of_bounds) else if len < 0 || start < 0 || start > STRING.length s then raise Out_of_bounds else Empty | Concat(l,cl,r,cr,_) -> if start < 0 || len < 0 || start + len > cl + cr then raise Out_of_bounds; let left = if start = 0 then if len >= cl then l else sub 0 len l else if start > cl then Empty else if start + len >= cl then sub start (cl - start) l else sub start len l in let right = if start <= cl then let upto = start + len in if upto = cl + cr then r else if upto < cl then Empty else sub 0 (upto - cl) r else sub (start - cl) len r in concat left right let insert start rope r = concat (concat (sub 0 start r) rope) (sub start (length r - start) r) let remove start len r = concat (sub 0 start r) (sub (start + len) (length r - start - len) r) let to_string r = let rec strings l = function Empty -> l | Leaf s -> s :: l | Concat(left,_,right,_,_) -> strings (strings l right) left in string_of_string_list (strings [] r) let rec iter f = function Empty -> () | Leaf s -> STRING.iter f s | Concat(l,_,r,_,_) -> iter f l; iter f r let iteri f r = let rec aux f i = function Empty -> () | Leaf s -> for j = 0 to STRING.length s - 1 do f (i + j) (STRING.unsafe_get s j) done | Concat(l,cl,r,_,_) -> aux f i l; aux f (i + cl) r in aux f 0 r let rec rangeiter f start len = function Empty -> if start <> 0 || len <> 0 then raise Out_of_bounds | Leaf s -> let n = start + len in let lens = STRING.length s in if start >= 0 && len >= 0 && n <= lens then for i = start to n - 1 do f (STRING.unsafe_get s i) done else raise Out_of_bounds | Concat(l,cl,r,cr,_) -> if start < 0 || len < 0 || start + len > cl + cr then raise Out_of_bounds; if start < cl then begin let upto = start + len in if upto <= cl then rangeiter f start len l else begin rangeiter f start (cl - start) l; rangeiter f 0 (upto - cl) r end end else begin rangeiter f (start - cl) len r end let rec fold f a = function Empty -> a | Leaf s -> let acc = ref a in for i = 0 to STRING.length s - 1 do acc := f !acc (STRING.unsafe_get s i) done; !acc | Concat(l,_,r,_,_) -> fold f (fold f a l) r (* =end *) |
From: ChriS <chr...@us...> - 2007-08-11 01:47:56
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv17373 Modified Files: Makefile rope.ml Log Message: Added benchmark suite developed by Mauricio Fernandez and myself. Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** rope.ml 11 Aug 2007 01:15:16 -0000 1.4 --- rope.ml 11 Aug 2007 01:47:53 -0000 1.5 *************** *** 533,540 **** ! let sub r i len = ! if i < 0 || len < 0 || i > length r - len then invalid_arg "Rope.sub" else if len = 0 then empty ! else sub_rec i len r --- 533,542 ---- ! let sub rope i len = ! let len_rope = length rope in ! if i < 0 || len < 0 || i > len_rope - len then invalid_arg "Rope.sub" else if len = 0 then empty ! else if len <= 1024 && len_rope >= 16384 then flatten_subrope rope i len ! else sub_rec i len rope *************** *** 664,686 **** } - (* [rewind_path i path] return the tail of the path s.t. the first - element of the tail contains the global location [i] -- one must - then search for the leaf from there. *) - let rec rewind_path itr i = function - | [] -> assert false - | ((node, g0) :: tl) as path -> - if i < g0 || g0 + length node <= i then rewind_path itr i tl - else set_current_for_index_rec itr path g0 (i - g0) node (* [g0] is the global index (of [itr.rope]) of the beginning of the ! node we are examining (the first of the [path]). [i] is the _local_ index (of the current node) that we seek the leaf for *) ! and set_current_for_index_rec itr path g0 i = function | Sub(s, i0, len) -> assert(0 <= i && i < len); - itr.path <- path; - (* we do not need to add the [Sub] node to the path because - when we will rewind it, we are sure the index will not be - in the leaf. *) itr.current <- s; itr.current_g0 <- g0; --- 666,676 ---- } (* [g0] is the global index (of [itr.rope]) of the beginning of the ! node we are examining. [i] is the _local_ index (of the current node) that we seek the leaf for *) ! let rec set_current_for_index_rec itr g0 i = function | Sub(s, i0, len) -> assert(0 <= i && i < len); itr.current <- s; itr.current_g0 <- g0; *************** *** 688,702 **** itr.current_offset <- i0 - g0 | Concat(_, len, l,ll, r) -> ! if i < ll then ! let path = (l, g0) :: path in ! set_current_for_index_rec itr path g0 i l ! else ! let g0 = g0 + ll in ! let path = (r, g0) :: path in ! set_current_for_index_rec itr path g0 (i - ll) r let set_current_for_index itr = ! (* rewind_path itr itr.i itr.path *) ! set_current_for_index_rec itr [] 0 itr.i itr.rope let rope itr = itr.rope --- 678,686 ---- itr.current_offset <- i0 - g0 | Concat(_, len, l,ll, r) -> ! if i < ll then set_current_for_index_rec itr g0 i l ! else set_current_for_index_rec itr (g0 + ll) (i - ll) r let set_current_for_index itr = ! set_current_for_index_rec itr 0 itr.i itr.rope let rope itr = itr.rope Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/Makefile,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** Makefile 11 Aug 2007 01:15:16 -0000 1.2 --- Makefile 11 Aug 2007 01:47:53 -0000 1.3 *************** *** 25,28 **** --- 25,32 ---- unix.cmxa benchmark.cmxa $^ + .PHONY: bench + bench: rope.cmxa + cd bench; $(MAKE) + doc: $(wildcard *.mli) [ -d "$@" ] || mkdir $@ *************** *** 100,101 **** --- 104,106 ---- rm -rf doc/ find . -type f -perm -u=x -exec rm -f {} \; + cd bench; $(MAKE) clean \ No newline at end of file |
From: ChriS <chr...@us...> - 2007-08-11 01:46:47
|
Update of /cvsroot/ocaml-rope/rope/bench In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv16994/bench Log Message: Directory /cvsroot/ocaml-rope/rope/bench added to the repository |
From: ChriS <chr...@us...> - 2007-08-11 01:15:15
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv4808 Modified Files: Makefile rope.ml rope.mli Log Message: Trying to improve the Iterator. Saving the path to the leaf does not lead to an imrpivement. Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** rope.ml 10 Aug 2007 19:29:26 -0000 1.3 --- rope.ml 11 Aug 2007 01:15:16 -0000 1.4 *************** *** 53,57 **** type rope = t ! let max_flatten_length = 40 (** Ropes of length [<= max_flatten_length] may be flattened by [concat2]. [max_flatten_length] must be quite --- 53,57 ---- type rope = t ! let max_flatten_length = 32 (** Ropes of length [<= max_flatten_length] may be flattened by [concat2]. [max_flatten_length] must be quite *************** *** 93,97 **** with Exit -> m, !i ! let height_to_rebalance = max_height (* Beyond this height, implicit balance will be done. This value allows gross inefficiencies while not being too time consuming. --- 93,97 ---- with Exit -> m, !i ! let rebalancing_height = max_height - 1 (* Beyond this height, implicit balance will be done. This value allows gross inefficiencies while not being too time consuming. *************** *** 218,246 **** ***********************************************************************) ! (* [rope2] is a small rope and will be forced to concatenate with the ! right leaf of rope1. *) ! let rec balance_concat_absorb rope1 rope2 len2 = ! match rope1 with ! | Sub(s1, i1, lens1) -> ! let len = lens1 + len2 in ! (* if len > 1024 then failwith "balance_concat_absorb"; *) ! let s = String.create len in ! String.blit s1 i1 s 0 lens1; ! copy_to_substring s lens1 rope2; ! Sub(s, 0, len) ! | Concat(h, len, l,ll, r) -> ! Concat(h, len + len2, l,ll, balance_concat_absorb r rope2 len2) ! ! let balance_concat_fast rope1 rope2 = ! let len1 = length rope1 ! and len2 = length rope2 in ! if len1 = 0 then rope2 ! else if len2 = 0 then rope1 ! else ! let h = 1 + max (height rope1) (height rope2) in ! Concat(h, len1 + len2, rope1, len1, rope2) ! ! (* [balance_concat] is a simple concat. Flattening is done during the ! balancing (to avoid reflattening at each concat). *) let balance_concat rope1 rope2 = let len1 = length rope1 --- 218,222 ---- ***********************************************************************) ! (* Fast, no fuss, concatenation. *) let balance_concat rope1 rope2 = let len1 = length rope1 *************** *** 248,259 **** if len1 = 0 then rope2 else if len2 = 0 then rope1 - else if len2 <= 16 then - try balance_concat_absorb rope1 rope2 len2 - with _ -> let h = 1 + max (height rope1) (height rope2) in - Concat(h, len1 + len2, rope1, len1, rope2) else let h = 1 + max (height rope1) (height rope2) in Concat(h, len1 + len2, rope1, len1, rope2) - ;; (* Invariants for [forest]: --- 224,230 ---- *************** *** 275,281 **** while len > min_length.(!n + 1) do if is_not_empty forest.(!n) then ( ! sum := balance_concat_fast forest.(!n) !sum; forest.(!n) <- empty; ); incr n done; --- 246,253 ---- while len > min_length.(!n + 1) do if is_not_empty forest.(!n) then ( ! sum := balance_concat forest.(!n) !sum; forest.(!n) <- empty; ); + if !n = level_flatten then sum := flatten !sum; incr n done; *************** *** 324,328 **** let concat_forest forest = let concat (n, sum) r = ! let sum = balance_concat_fast r sum in (n+1, if n = level_flatten then flatten sum else sum) in snd(Array.fold_left concat (0,empty) forest) --- 296,300 ---- let concat_forest forest = let concat (n, sum) r = ! let sum = balance_concat r sum in (n+1, if n = level_flatten then flatten sum else sum) in snd(Array.fold_left concat (0,empty) forest) *************** *** 339,357 **** concat_forest forest let balance_if_needed r = ! (* if height r >= height_to_rebalance then balance r else r *) ! let h = height r in ! if h >= height_to_rebalance || length r < min_length.(h) then balance r ! else r ! ;; (** "Fast" concat for ropes. ********************************************************************** ! Since concat is one of the few ways a rope can be constructed, it ! must be fast. Also, this means it is this concat which is ! responsible for the height of small ropes (until balance kicks in ! but the later the better). ! *) (* Try to relocate the [leaf] at a position that will not increase the --- 311,328 ---- concat_forest forest + (* Only rebalance on the height. Also doing it when [length r + < min_length.(height r)] ask for too many balancing and thus is slower. *) let balance_if_needed r = ! if height r >= rebalancing_height then balance r else r ! (** "Fast" concat for ropes. ********************************************************************** ! * Since concat is one of the few ways a rope can be constructed, it ! * must be fast. Also, this means it is this concat which is ! * responsible for the height of small ropes (until balance kicks in ! * but the later the better). ! *) (* Try to relocate the [leaf] at a position that will not increase the *************** *** 496,504 **** failwith "Rope.concat2: the length of the resulting rope exceeds max_int"; let h = 1 + max (height rope1) (height rope2) in ! if h >= height_to_rebalance then (* We will need to rebalance anyway, so do a simple concat *) balance (Concat(h, len, rope1, len1, rope2)) else ! (* No automatic rebalancing *) concat2_nonempty rope1 rope2 end --- 467,475 ---- failwith "Rope.concat2: the length of the resulting rope exceeds max_int"; let h = 1 + max (height rope1) (height rope2) in ! if h >= rebalancing_height then (* We will need to rebalance anyway, so do a simple concat *) balance (Concat(h, len, rope1, len1, rope2)) else ! (* No automatic rebalancing -- experimentally lead to faster exec *) concat2_nonempty rope1 rope2 end *************** *** 675,682 **** type t = { ! r: rope; ! len: int; (* = length r; avoids to recompute it again and again *) mutable i: int; (* current position in the rope; it is always a valid position of the rope or [-1]. *) mutable current: string; (* local cache of current leaf *) mutable current_g0: int; --- 646,657 ---- type t = { ! rope: rope; ! len: int; (* = length rope; avoids to recompute it again and again ! for bound checks *) mutable i: int; (* current position in the rope; it is always a valid position of the rope or [-1]. *) + mutable path: (rope * int) list; + (* path to the current leaf with global range. First elements are + closer to the leaf, last element is the full rope. *) mutable current: string; (* local cache of current leaf *) mutable current_g0: int; *************** *** 689,717 **** } ! let rec set_current_for_index_rec itr g0 i = function | Sub(s, i0, len) -> assert(0 <= i && i < len); itr.current <- s; itr.current_g0 <- g0; itr.current_g1 <- g0 + len; itr.current_offset <- i0 - g0 ! | Concat(_, _, l,ll, r) -> ! if i < ll then set_current_for_index_rec itr g0 i l ! else set_current_for_index_rec itr (g0 + ll) (i - ll) r ! let rope itr = itr.r let make r i0 = let len = length r in let itr = ! { r = r; len = len; i = i0; current = ""; current_offset = 0; current_g0 = 0; current_g1 = 0; ! (* empty range, important if not set! *) } in if i0 >= 0 && i0 < len then ! set_current_for_index_rec itr 0 i0 r; (* force [current] to be set *) itr --- 664,718 ---- } ! (* [rewind_path i path] return the tail of the path s.t. the first ! element of the tail contains the global location [i] -- one must ! then search for the leaf from there. *) ! let rec rewind_path itr i = function ! | [] -> assert false ! | ((node, g0) :: tl) as path -> ! if i < g0 || g0 + length node <= i then rewind_path itr i tl ! else set_current_for_index_rec itr path g0 (i - g0) node ! ! (* [g0] is the global index (of [itr.rope]) of the beginning of the ! node we are examining (the first of the [path]). ! [i] is the _local_ index (of the current node) that we seek the leaf for *) ! and set_current_for_index_rec itr path g0 i = function | Sub(s, i0, len) -> assert(0 <= i && i < len); + itr.path <- path; + (* we do not need to add the [Sub] node to the path because + when we will rewind it, we are sure the index will not be + in the leaf. *) itr.current <- s; itr.current_g0 <- g0; itr.current_g1 <- g0 + len; itr.current_offset <- i0 - g0 ! | Concat(_, len, l,ll, r) -> ! if i < ll then ! let path = (l, g0) :: path in ! set_current_for_index_rec itr path g0 i l ! else ! let g0 = g0 + ll in ! let path = (r, g0) :: path in ! set_current_for_index_rec itr path g0 (i - ll) r ! let set_current_for_index itr = ! (* rewind_path itr itr.i itr.path *) ! set_current_for_index_rec itr [] 0 itr.i itr.rope ! ! let rope itr = itr.rope let make r i0 = let len = length r in let itr = ! { rope = balance_if_needed r; len = len; i = i0; + path = [(r, 0)]; (* the whole rope *) current = ""; current_offset = 0; current_g0 = 0; current_g1 = 0; ! (* empty range, important if [current] not set! *) } in if i0 >= 0 && i0 < len then ! set_current_for_index itr; (* force [current] to be set *) itr *************** *** 720,726 **** else ( if itr.current_g0 <= i && i < itr.current_g1 then ! String.get itr.current (i + itr.current_offset) else ! get itr.r i (* rope get *) ) --- 721,727 ---- else ( if itr.current_g0 <= i && i < itr.current_g1 then ! itr.current.[i + itr.current_offset] else ! get itr.rope i (* rope get *) ) *************** *** 730,735 **** else ( if i < itr.current_g0 || i >= itr.current_g1 then ! set_current_for_index_rec itr 0 i itr.r; (* out of local bounds *) ! String.get itr.current (i + itr.current_offset) ) --- 731,736 ---- else ( if i < itr.current_g0 || i >= itr.current_g1 then ! set_current_for_index itr; (* out of local bounds *) ! itr.current.[i + itr.current_offset] ) *************** *** 1000,1008 **** let rem_len = len - buf_i1 in while buf_i1 > min_length.(!n + 1) && length !sum < rem_len do ! sum := balance_concat_fast b.forest.(!n) !sum; if !n = level_flatten then sum := flatten !sum; incr n done; ! sum := balance_concat_fast !sum (Sub(String.sub b.buf 0 buf_i1, 0, buf_i1)) ) else ( --- 1001,1009 ---- let rem_len = len - buf_i1 in while buf_i1 > min_length.(!n + 1) && length !sum < rem_len do ! sum := balance_concat b.forest.(!n) !sum; if !n = level_flatten then sum := flatten !sum; incr n done; ! sum := balance_concat !sum (Sub(String.sub b.buf 0 buf_i1, 0, buf_i1)) ) else ( *************** *** 1017,1021 **** while length !sum < len do assert(!n < max_height); ! sum := balance_concat_fast b.forest.(!n) !sum; (* FIXME: Check how this line may generate a 1Mb leaf: *) (* if !n = level_flatten then sum := flatten !sum; *) --- 1018,1022 ---- while length !sum < len do assert(!n < max_height); ! sum := balance_concat b.forest.(!n) !sum; (* FIXME: Check how this line may generate a 1Mb leaf: *) (* if !n = level_flatten then sum := flatten !sum; *) *************** *** 1058,1063 **** external input_scan_line : in_channel -> int = "caml_ml_input_scan_line" ! let input_line ?(leaf_size=128) chan = ! let b = Buffer.create leaf_size in let rec scan () = let n = input_scan_line chan in --- 1059,1064 ---- external input_scan_line : in_channel -> int = "caml_ml_input_scan_line" ! let input_line ?(leaf_length=128) chan = ! let b = Buffer.create leaf_length in let rec scan () = let n = input_scan_line chan in Index: Makefile =================================================================== RCS file: /cvsroot/ocaml-rope/rope/Makefile,v retrieving revision 1.1.1.1 retrieving revision 1.2 diff -C2 -d -r1.1.1.1 -r1.2 *** Makefile 9 Aug 2007 17:24:55 -0000 1.1.1.1 --- Makefile 11 Aug 2007 01:15:16 -0000 1.2 *************** *** 1,3 **** --- 1,5 ---- VERSION=0.2 + SF_WEB = /home/groups/o/oc/ocaml-rope/htdocs + SRC_WEB = NONE UNSAFE=-unsafe -noassert # speed gained by this is small *************** *** 35,38 **** --- 37,61 ---- + # Release a Sourceforge tarball and publish the HTML doc + .PHONY: web upload + web: doc + @ if [ -d doc ] ; then \ + scp -r doc/ shell.sf.net:$(SF_WEB)/ \ + && echo "*** Published documentation on SF" ; \ + fi + @ if [ -d $(SRC_WEB)/ ] ; then \ + scp $(SRC_WEB)/*.html $(SRC_WEB)/*.jpg LICENSE \ + shell.sf.net:$(SF_WEB) \ + && echo "*** Published web site ($(SRC_WEB)/) on SF" ; \ + fi + + upload: dist + @ if [ -z "$(PKG_TARBALL)" ]; then \ + echo "PKG_TARBALL not defined"; exit 1; fi + echo -e "bin\ncd incoming\nput $(PKG_TARBALL)" \ + | ncftp -p chr...@us... upload.sourceforge.net \ + && echo "*** Uploaded $(PKG_TARBALL) to SF" + + OCAMLC ?= ocamlc OCAMLOPT ?= ocamlopt Index: rope.mli =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.mli,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** rope.mli 10 Aug 2007 19:29:26 -0000 1.2 --- rope.mli 11 Aug 2007 01:15:16 -0000 1.3 *************** *** 18,27 **** ! (** Ropes are a scalable string implementation: they are designed for ! efficient operation that involve the string as a whole. ! Operations such as concatenation, and substring take time that is ! nearly independent of the length of the string. Unlike strings, ! ropes are a reasonable representation for very long strings such ! as edit buffers or mail messages. Advantages: --- 18,28 ---- ! (** Ropes ("heavyweight strings") are a scalable string ! implementation: they are designed for efficient operation that ! involve the string as a whole. Operations such as concatenation, ! and substring take time that is nearly independent of the length ! of the string. Unlike strings, ropes are a reasonable ! representation for very long strings such as edit buffers or mail ! messages. Advantages: *************** *** 200,204 **** library [Pervasives]. *) ! val input_line : ?leaf_size:int -> in_channel -> t (** Read characters from the given input channel, until a newline character is encountered. Return the rope of all characters read, --- 201,205 ---- library [Pervasives]. *) ! val input_line : ?leaf_length:int -> in_channel -> t (** Read characters from the given input channel, until a newline character is encountered. Return the rope of all characters read, *************** *** 245,251 **** val height : t -> int (** [depth r] returns the depth of the rope [r]. This information ! may be useful to decide whether you want to re-balance. This is ! implementation dependent and may change from one version to the ! next. *) --- 246,254 ---- val height : t -> int (** [depth r] returns the depth of the rope [r]. This information ! may be useful to decide whether you want to re-balance. *) ! ! val rebalancing_height : int ! (** The rope will be rebalanced by some functions it its height is ! greater or equal to [rebalancing_height]. *) |
From: ChriS <chr...@us...> - 2007-08-10 19:29:25
|
Update of /cvsroot/ocaml-rope/rope In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv1984 Modified Files: rope.ml rope.mli Added Files: .cvsignore Log Message: When balancing, try to force small ropes to be absorbed by the leaves of bigger ropes. For the record: that does not seem to be an improvement. --- NEW FILE: .cvsignore --- *.annot *.cmi *.cmo *.cmx *.cma *.cmxa Index: rope.ml =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.ml,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** rope.ml 9 Aug 2007 20:27:21 -0000 1.2 --- rope.ml 10 Aug 2007 19:29:26 -0000 1.3 *************** *** 53,57 **** type rope = t ! let max_flatten_length = 32 (** Ropes of length [<= max_flatten_length] may be flattened by [concat2]. [max_flatten_length] must be quite --- 53,57 ---- type rope = t ! let max_flatten_length = 40 (** Ropes of length [<= max_flatten_length] may be flattened by [concat2]. [max_flatten_length] must be quite *************** *** 183,188 **** t ! (* Flatten a rope. Same as [of_string(ro_string r)], just faster and ! avoid unecessary copying. *) let flatten r = match r with | Sub(_,_,_) -> r --- 183,187 ---- t ! (* Flatten a rope (avoids unecessary copying). *) let flatten r = match r with | Sub(_,_,_) -> r *************** *** 219,222 **** --- 218,244 ---- ***********************************************************************) + (* [rope2] is a small rope and will be forced to concatenate with the + right leaf of rope1. *) + let rec balance_concat_absorb rope1 rope2 len2 = + match rope1 with + | Sub(s1, i1, lens1) -> + let len = lens1 + len2 in + (* if len > 1024 then failwith "balance_concat_absorb"; *) + let s = String.create len in + String.blit s1 i1 s 0 lens1; + copy_to_substring s lens1 rope2; + Sub(s, 0, len) + | Concat(h, len, l,ll, r) -> + Concat(h, len + len2, l,ll, balance_concat_absorb r rope2 len2) + + let balance_concat_fast rope1 rope2 = + let len1 = length rope1 + and len2 = length rope2 in + if len1 = 0 then rope2 + else if len2 = 0 then rope1 + else + let h = 1 + max (height rope1) (height rope2) in + Concat(h, len1 + len2, rope1, len1, rope2) + (* [balance_concat] is a simple concat. Flattening is done during the balancing (to avoid reflattening at each concat). *) *************** *** 226,232 **** --- 248,259 ---- if len1 = 0 then rope2 else if len2 = 0 then rope1 + else if len2 <= 16 then + try balance_concat_absorb rope1 rope2 len2 + with _ -> let h = 1 + max (height rope1) (height rope2) in + Concat(h, len1 + len2, rope1, len1, rope2) else let h = 1 + max (height rope1) (height rope2) in Concat(h, len1 + len2, rope1, len1, rope2) + ;; (* Invariants for [forest]: *************** *** 248,255 **** while len > min_length.(!n + 1) do if is_not_empty forest.(!n) then ( ! sum := balance_concat forest.(!n) !sum; forest.(!n) <- empty; ); - if !n = level_flatten then sum := flatten !sum; incr n done; --- 275,281 ---- while len > min_length.(!n + 1) do if is_not_empty forest.(!n) then ( ! sum := balance_concat_fast forest.(!n) !sum; forest.(!n) <- empty; ); incr n done; *************** *** 298,302 **** let concat_forest forest = let concat (n, sum) r = ! let sum = balance_concat r sum in (n+1, if n = level_flatten then flatten sum else sum) in snd(Array.fold_left concat (0,empty) forest) --- 324,328 ---- let concat_forest forest = let concat (n, sum) r = ! let sum = balance_concat_fast r sum in (n+1, if n = level_flatten then flatten sum else sum) in snd(Array.fold_left concat (0,empty) forest) *************** *** 314,318 **** let balance_if_needed r = ! if height r >= height_to_rebalance then balance r else r ;; --- 340,347 ---- let balance_if_needed r = ! (* if height r >= height_to_rebalance then balance r else r *) ! let h = height r in ! if h >= height_to_rebalance || length r < min_length.(h) then balance r ! else r ;; *************** *** 368,371 **** --- 397,402 ---- ;; + (* We avoid copying too much -- as this may slow down access, even if + height is lower. *) let rec concat2_nonempty rope1 rope2 = match rope1, rope2 with *************** *** 474,486 **** ;; ! (** Subrope and other ops ***********************************************************************) (* Are lazy sub-rope nodes really needed? *) (* This function assumes that [i], [len] define a valid sub-rope of ! the last arg. *) let rec sub_rec i len = function ! | Sub(s, i0, slen) -> ! assert(i >= 0 && i <= slen - len); Sub(s, i0 + i, len) | Concat(_, rope_len, l, ll, r) -> --- 505,541 ---- ;; ! (** Subrope ***********************************************************************) + let rec sub_to_substring flat j i len = function + | Sub(s, i0, lens) -> + assert(i >= 0 && i <= lens - len); + assert(j >= 0 && j + len <= String.length flat); + String.blit s (i0 + i) flat j len + | Concat(_, rope_len, l, ll, r) -> + let ri = i - ll in + if ri >= 0 then (* only right branch *) + sub_to_substring flat j ri len r + else (* ri < 0 *) + let lenr = ri + len in + if lenr <= 0 then (* only left branch *) + sub_to_substring flat j i len l + else ( (* at least one char from the left and right branches *) + sub_to_substring flat j i (-ri) l; + sub_to_substring flat (j - ri) 0 lenr r; + ) + + let flatten_subrope rope i len = + let flat = String.create len in + sub_to_substring flat 0 i len rope; + Sub(flat, 0, len) + ;; + (* Are lazy sub-rope nodes really needed? *) (* This function assumes that [i], [len] define a valid sub-rope of ! the last arg. *) let rec sub_rec i len = function ! | Sub(s, i0, lens) -> ! assert(i >= 0 && i <= lens - len); Sub(s, i0 + i, len) | Concat(_, rope_len, l, ll, r) -> *************** *** 500,508 **** and r' = if rlen = rl then r else sub_rec 0 rlen r in let h = 1 + max (height l') (height r') in ! (* FIXME: do we have to use this opportunity to flatten ! some subtrees? concat2 ? In any case, the tree we get ! is no worse than the initial tree. *) Concat(h, len, l', -ri, r') let sub r i len = if i < 0 || len < 0 || i > length r - len then invalid_arg "Rope.sub" --- 555,565 ---- and r' = if rlen = rl then r else sub_rec 0 rlen r in let h = 1 + max (height l') (height r') in ! (* FIXME: do we have to use this opportunity to flatten some ! subtrees? In any case, the height of tree we get is no ! worse than the initial tree (but the length may be much ! smaller). *) Concat(h, len, l', -ri, r') + let sub r i len = if i < 0 || len < 0 || i > length r - len then invalid_arg "Rope.sub" *************** *** 511,514 **** --- 568,574 ---- + (** String alike functions + ***********************************************************************) + (* Return the index of [c] in [s.[i .. i1-1]] plus the [offset] or [-1] if not found. *) *************** *** 940,948 **** let rem_len = len - buf_i1 in while buf_i1 > min_length.(!n + 1) && length !sum < rem_len do ! sum := balance_concat b.forest.(!n) !sum; if !n = level_flatten then sum := flatten !sum; incr n done; ! sum := balance_concat !sum (Sub(String.sub b.buf 0 buf_i1, 0, buf_i1)) ) else ( --- 1000,1008 ---- let rem_len = len - buf_i1 in while buf_i1 > min_length.(!n + 1) && length !sum < rem_len do ! sum := balance_concat_fast b.forest.(!n) !sum; if !n = level_flatten then sum := flatten !sum; incr n done; ! sum := balance_concat_fast !sum (Sub(String.sub b.buf 0 buf_i1, 0, buf_i1)) ) else ( *************** *** 957,962 **** while length !sum < len do assert(!n < max_height); ! sum := balance_concat b.forest.(!n) !sum; ! if !n = level_flatten then sum := flatten !sum; incr n done; --- 1017,1023 ---- while length !sum < len do assert(!n < max_height); ! sum := balance_concat_fast b.forest.(!n) !sum; ! (* FIXME: Check how this line may generate a 1Mb leaf: *) ! (* if !n = level_flatten then sum := flatten !sum; *) incr n done; *************** *** 1041,1044 **** --- 1102,1130 ---- | Concat(_,_, l,_, r) -> 1 + number_concat l + number_concat r + let rec length_leaves = function + | Sub(_,_, len) -> (len, len) + | Concat(_,_, l,_, r) -> + let (min1,max1) = length_leaves l + and (min2,max2) = length_leaves r in + (min min1 min2, max max1 max2) + + + module IMap = Map.Make(struct + type t = int + let compare = Pervasives.compare + end) + + let distrib_leaves = + let rec add_leaves m = function + | Sub(_,_,len) -> + (try incr(IMap.find len !m) + with _ -> m := IMap.add len (ref 1) !m) + | Concat(_,_, l,_, r) -> add_leaves m l; add_leaves m r in + fun r -> + let m = ref(IMap.empty) in + add_leaves m r; + !m + + (**/**) Index: rope.mli =================================================================== RCS file: /cvsroot/ocaml-rope/rope/rope.mli,v retrieving revision 1.1.1.1 retrieving revision 1.2 diff -C2 -d -r1.1.1.1 -r1.2 *** rope.mli 9 Aug 2007 17:24:56 -0000 1.1.1.1 --- rope.mli 10 Aug 2007 19:29:26 -0000 1.2 *************** *** 391,394 **** --- 391,397 ---- val number_concat : t -> int val print : t -> unit + val length_leaves : t -> int * int + module IMap : Map.S with type key = int + val distrib_leaves : t -> int ref IMap.t (**/**) |