Showing posts with label Perl. Show all posts
Showing posts with label Perl. Show all posts

Saturday, July 12, 2008

Javascript Performance Considered as a Helix of Semi-Precious Hash Tables

I had a discussion about Javascript performance the other day, which reminded me that the more things change, the more they stay the same. Some of the things casual Javascript programmers are grappling with today, were big research issues for IBM's
TOBEY compiler technology a few years ago. (And maybe still, for all I know.)

Let's start with the basics. Whenever you're referencing objects in Javascript, you're getting pointers, not deep copies. So:

var x = a.b.c.d.e;
x.something = 0;
x.something_else = 'foo';

is actually modifying attributes of the original a.b.c.d.e object.

Intuitively, you can see that you're saving bytes in the program, which means less time to transmit the script file, less time to parse, and saving space in the browser cache which could avoid re-fetching some page, image, or other resource later. But there are performance implications at a deeper level too.

Javascript's object orientation is like Perl's, based all on hash tables, except it doesn't hit you over the head with that fact. So x.y.z involves looking up the key 'y' in x's hash table, which returns another hash table, in which you look up the key 'z'.

Array notation and object notation are effectively interchangeable. x.foo works the same as x['foo']. x[0], x[1], x[2], etc. are not necessarily contiguous in memory, they're just entries in a hash table whose keys happen to be integers. Looping through an array involves a hash table lookup each time, not just incrementing a pointer.

The scoping and closure features in Javascript, plus its interpreted nature, mean it has to do more lookups to figure out how to resolve each variable reference. For example:

function foo()
{
var a, x;

function bar()
{
var a, y;

for (...)
{
var a, z;

a = 1;
// a is found in current scope, requiring just one hash table lookup.
x = 'hello';
// x is not found in current scope;
// x is not found in parent scope;
// x _is_ found in grandparent scope.
// Meaning 3 hash table lookups to figure out where x is.

When all these slight variations in efficiency get put inside loops or frequently called functions, that's when the performance can start to drag. That's why you see people doing things like:

for (var i = 0, limit = some_object.length; i < limit; i++) ...

If i is declared outside the loop, each reference to it to test or increment means having to find it in some outer scope. If some_object.length is referenced in the loop bounds test, each time through the loop has to locate some_object in the right scope, plus do another hash table lookup to retrieve the length property. The length property could be modified by code inside the loop, so even though you consider some_object.length to be a constant value, Javascript can't assume the same.

Getting back to the notion of our first example, when you store a pointer to some deeply nested object and refer directly to that object, multiple times:

var it = x.y.z.style;
it.marginTop = "0em";
it.marginBottom = "1em";
it.marginLeft = "1em";
it.marginRight = "2em";

you're saving all those lookups, both for scope and traversing the hash tables of object members, for each reference.

At the DOM level, you've got a property element.childNodes and a method element.hasChildNodes(). Seems intuitive that checking for the existence of child nodes should be faster than returning the actual nodes, right?

Remember, childNodes is just giving you a pointer to a data structure that is being maintained continuously, not making a copy of anything, or assembling the structure on-demand. So the overhead in each case is constant. That data structure could be empty, which is why the has*() method could be useful. There's a distinction sometimes between "this object exists" and "this object contains something useful", so you wind up doing things like:

els = document.getElementsByTagName('a');
if (els && els.length > 0) ...
// Must test that the assignment succeeded,
// _and_ that what came back wasn't an empty structure

Thursday, May 29, 2008

How PL/SQL Could Be More Like Perl

An idea has been rattling around in my head for a while now. I know, I know, there's a lot of empty space so it makes a lot of noise. :-) Could PL/SQL become more popular and easier to use by taking a couple of points from the Perl playbook?

I read a blog post about how scripting languages are or aren't gaining on Java. I think supporting curly-brace syntax would be a nifty way to encourage PL/SQL adoption among both scripters and Java coders. But maybe that's just me.

My first impressions of Ada and then PL/SQL were somewhat negative: hey, this verbose BEGIN/END, IF...THEN...END IF syntax reminds me of Pascal. I first programmed in Pascal on the Commodore 64, and it was deadly slow to compile and run, owing to the whole UCSD P-Code business. Then at university, it was the first language for coursework, and even though it ran really fast on UNIX boxes, I always felt that behind the scenes, more deadly slowness was occurring.

These days, 95% of the languages I code in use curly braces for blocks:

if ... { ... }
function ... { ... }
for ... { ... }

Imagine if PL/SQL did the same. Suddenly, brace matching in vi/vim would work. (Hit % while cursor is on a brace character to find the matching brace at the other end of the block.) It would be unlikely to introduce logic errors; in my experience, mis-nesting of blocks is not a frequent source of errors in Perl or Java, and in deeply nested PL/SQL, even today a careless coder can just add END IF statements until the syntax error goes away. I sometimes write little comments after the END IF, END LOOP, etc. to remind myself of which block each one closes.

On the documentation end, the PL/SQL User's Guide and Reference, aka PL/SQL Language Reference in 11g, has never devoted reference topics specifically to "BEGIN Statement", "END Statement", "END IF Statement", etc. Instead there are generic topics like "Block Declaration", or a section on "LOOP Statements" that doesn't split out the "END..." part as a separate item. That's always made it hard for me to write auto-linking pretty printers for PL/SQL (i.e. no "BEGIN" topic to link from the "BEGIN" keyword), but it would make syntax enhancements slot right into the docs.

From a parsing standpoint, I think it's pretty straightforward. If you leave out a THEN or put an END IF where an END LOOP is expected, PL/SQL gives you a straightforward error message. It knows what block is open and what the expected closing symbol is. So I imagine that it's practical to parse syntax like:

procedure foo is
x number;
{
if 1 > 0
{
for bar in (select * from t1)
{
x := 3.1;
declare
x varchar2(64);
{
x := 'hello';
}
}
}
}


{ takes the place of THEN, LOOP, and BEGIN. If a { is seen where one of those tokens is expected, treat it like the equivalent block beginning keyword. When a } is seen, treat it like whatever block closing keyword is valid at that spot. When a { is seen with nothing special preceding it, treat it like a nested BEGIN.

When I think about it more deeply, I see potential problems around ELSE and WHEN clauses, where those keywords act as both the end of one block and the beginning of another, but anyway this whole idea is probably just a fantasy on my part.

One other Perlism that really struck home lately. Perl lets you get away with a comma after the last item within an array-style declaration. This seems like a minor point, but when writing programs that generate other programs (or anyway JSON-style data structures), it is sometimes difficult to give special treatment to the first or last data item. For example, with SQL or PL/SQL it's simple to write out 1000 INSERT statements, each ending with a semicolon. But let's say you have an XSLT transform with a FOR-EACH loop that produces an initialization statement for a data structure. The output goes

'item1',
'item2',
'item3',
...
'itemN',

and then you're left with that final trailing comma that you need to get rid of somehow. I'll often put the comma at the beginning of each line for just that reason, and to allow easier reordering of parameters and such. But then the first item is a special case. Think of how many times you have to introduce a Boolean variable to make the output slightly different for the first or last pass through a loop.

I used to think Perl's optional no-op trailing comma was just a flippant design choice, but now I think it was a very shrewd way to make dynamic programming easier. One that some other languages could emulate.

Tuesday, March 11, 2008

Can Your Programming Language Do This... Or That...

Just wanted to point out this "Joel On Software" article, Can Your Programming Language Do This?. It's a nice concise opinion that summarizes why, given an arbitrary algorithmic problem, I'm personally more likely to turn to Javascript (or Perl or another scripting language with the same feel) than Java.

The key for me with Java is this statement from Joel:

Java required you to create a whole object with a single method called a functor if you wanted to treat a function like a first class object. Combine that with the fact that many OO languages want you to create a whole file for each class, and it gets really klunky fast.

I think of Java's OO nature as "hard" object orientation, in that choices are relatively set in stone based on how class files are organized and how the code flows. You can make variants of a class that do whatever you want, but you might have to do a lot of advance planning.

Conversely, in Perl, you can do like so:

sub something
{
...one set of code...
}

sub something
{
...another set of code...
}

You can call something(), and it picks up the last definition. Which makes it very easy to change the behavior of a program by overriding a method right before you call it, or by swapping the order of 'require' lines, or what have you. I think of this as "soft" object orientation, because it may be less amenable to mathematical proof of correctness, but it requires less planning and is less likely to produce cascades of syntax errors. Define it, call it, redefine it, call the new thing.

Most languages have some sort of dynamic execution facility. For example, with PL/SQL it's the EXECUTE IMMEDIATE statement and the OPEN-FOR statement. Any time you see a language concatenating strings and executing the result, you need to watch out for potential security problems. Who gets to enter that string, could it be rigged to execute multiple statements instead of one, could different names be substituted so it operated on some object you didn't expect. PL/SQL has the USING clause to guard against such problems by using bind values. Still, the Javascript approach of passing around functions as parameters feels comfortable, because all the variations of those functions are defined in your own source code rather than combined from arbitrary strings.

Tuesday, June 26, 2007

What's the Capital of Abyssinia?

Few subjects provoke as much passion as the question of how to capitalize programming code.

You've got C-like languages where case is significant, but the discussion continues whether to string_words_along or JamWordsTogether. My own convention for PL/SQL is a bit idiosyncratic. I decide whether a particular subprogram is more procedural or more object-oriented, and use underscores or Camel case as appropriate for each one.

Then you've got lots of other languages, like PL/SQL, where case is not significant. But you'd still like to format source code for readability and comprehensibility. I commonly see the convention of reserved words in all caps, and lowercase for names of tables, variables, etc. That allows for some degree of consistency in documentation -- you can talk about "the IF statement" and the reserved word is easy to pick out even if the text is stripped of all formatting in a man page or an e-mail. But if Oracle ships packages like DBMS_OUTPUT, does it make sense to capitalize those names as if they're reserved, or treat them more like user-defined objects? Rather than drive myself to distraction, I use lowercase for everything in source code (after all, nobody ever accused C or Perl code of being hard to read... er... :-). When referring to reserved words in text, I use all-caps.

Now, I am well aware that there is an uppercase stigma attached to some languages. FORTRAN 77 was case-sensitive and got endless grief for that. (Why, I left my small-town roots rather than accept a job working in FORTRAN.) Fortran 90 enabled the use of lowercase, which was such a big deal that it was reflected in the language name. At IBM, where I eventually worked my way up to working on XL Fortran :-), it was common to switch within the same sentence: "The IBM Toronto Lab took over the FORTRAN mission, and released several Fortran compilers, while the mainframe FORTRAN products continued to be developed by the Santa Teresa lab". This after years of working on Ada, which also had an uppercase stigma because everyone assumes it should be ADA. (It's Ada, because it's an eponym not an acronym.)

There is some uppercase lurking inside the database. Issue create table foo and it will dutifully create a table named FOO, as you can see by 'select table_name from user_tables'. You can make the table be named FooBar by enclosing the name in double quotes: create table "FooBar". But then you have to put the quotes everywhere you refer to the table, so it's not worth the trouble except in unusual circumstances where you want to obscure the name, or have names identical except for case.

The tilt towards uppercase means you more often see code like this for doing case-insensitive matches:

select last_name from my_table where upper(last_name) like 'A%';

You could just as well write:

...lower(last_name) like 'a%';

and people might regard that line with more respect. These days, out of principle, I always use a regular expression instead:

select last_name from my_table where regexp_like(last_name,'^a','i');

In real code, anyway. On the command line, I still slip back into LIKE out of habit. It puzzles me a bit that SQL can't handle the BOOL... bool... Boolean datatype of PL/SQL, yet regexp_like is testing a Boolean condition without any comparison operator.

Friday, May 18, 2007

Quotable Quotes

Spare a kind thought for the hard-working yet underappreciated quotation mark. Single quotes or double quotes, you ask? Exactly!

If you're familiar with other languages such as Perl or Javascript, you probably intermix single and double quotes as needed. Double quotes around strings containing single quotes. Single quotes around Perl strings containing $ or @ characters, so they aren't interpolated as embedded variables.

With PL/SQL, you'll almost always use single quotes. The main exception is around identifier names, which you can enclose in double quotes if they contain special characters or if you need to force them into mixed case or lowercase:

execute immediate 'create table "My_Table" ...';

Without those double quotes, the new table would be known internally (in the USER_TABLES view, etc.) as MY_TABLE. The double quotes force the object name to be exactly as entered, meaning you would get an error from "select * from MY_TABLE" or "select * from my_table". (In this last case, the name my_table is translated silently to MY_TABLE.)

So, that's it then. Use single quotes for string literals, nothing more to learn.

var1 := 'Hello world!';

But what happens when we start dealing with real-world cases?

var2 := 'Oracle Database Administrator''s Guide';

Wait a second! What's with the 2 consecutive single quotes? That's the notation to escape a single quote inside a string literal. What a bother. If you want to generate a text file with a bunch of insert statements, you have to run a search/replace on each string to create 2 of each single quote. And you have to do it before wrapping single quotes around the data. When done in PL/SQL, this leads to one of my favourite PL/SQL statements of all time:

var3 := replace(var2,'''','''''');

We are only replacing 1 single quote with 2 single quotes, but between the surrounding quotes for the literals and the doubled quotes to escape them inside the literals, it looks like an entry in the Obfuscated C Contest.

Luckily, in Oracle 10g there is a way to avoid all the escaping. It still requires you to predict what characters your string might contain, but within that constraint it is much more readable:

var4 := q'{Oracle Database Administrator's Guide}';
var5 := q'[I'm the king of the world!]';
var6 := q'#Mommy's all right, Daddy's all right...#';

With the q literal notation, the first and last characters inside the quotes are not part of the string value, and single quotes are OK since you are making sure that the closing sequence (in the examples above, }', ]', and #') do not appear anywhere in the string. If the opening character after the q' is a "bracket"-style character, the matching end character is the corresponding close bracket. If the opening character is some other punctuation mark or what have you, the same character is used immediately before a single quote to end the literal.

Where this really comes into play is in writing out code of one kind or another from PL/SQL. In a web application, you might be writing out HTML full of double quotes, Javascript full of single quotes, or a combination:

obj.innerHTML = '<div style="float: right;">';

It's very comforting to know you can wrap the whole thing in a PL/SQL string literal without doing any replacements inside the string:

var7 := q'|obj.innerHTML = '<div style="float: right;">';|';

Again, you'll have to know based on your own coding conventions or a priori that the closing delimiter character doesn't appear immediately before a single quote.

I like to combine this technique with a SQL*Plus trick I mentioned in an earlier post:

var8 :=
q'|
@javascript_source.js;
|';

Now that Javascript is available to PL/SQL and can be plunked into a web page, concatenated with other source, searched/replaced, etc. It doesn't have to contain any escaped '' sequences and so can be reused with other languages, edited by a non-PL/SQL programmer, run through a Javascript validator, or anything else that strikes your fancy.

Saturday, May 5, 2007

Perl vs. PL/SQL: Regular Expressions

One recent addition to Oracle's SQL dialect, and also PL/SQL, is Perl-like regular expressions.

It's very convenient to declare a CHECK constraint as a regular expression, using the REGEXP_LIKE operator. The data has to match a pattern, or it doesn't get into the database. The pattern could be all caps or all lowercase, some set of allowed characters, alphanumeric values with certain patterns, and so on.

It's also very convenient to set up a trigger that does a replace using regular expressions, using REGEXP_REPLACE instead of a combination of SUBSTR, TRIM, and REPLACE stretching out over dozens of lines. Back-references are particularly useful, say for recognizing a flexible pattern within a block of HTML and enclosing that pattern in tags for highlighting.

A couple of things are not quite ideal yet in the PL/SQL implementation. I have found that running REGEXP_REPLACE on certain moderately large strings can fail (and I've opened a bug for that). I wish there were more metacharacters supported; in the name of NLS, some \ sequences familiar from Perl are left out. And I am having an issue that I haven't fully diagnosed yet, doing backreferences in a pattern containing multiply nested parentheses.

Don't have code at hand to post samples; I'll try to come back to that later.

Saturday, April 21, 2007

Perl vs. PL/SQL

When I started learning PL/SQL, I was gratified to find that my whole Perl way of working translated easily into doing stored procedures.

Most small Perl scripts that do transformations are built around a loop like this:

@lines = ; # read entire contents of file
for $line (@lines)
{
# do some search/replace on each line
# print the result, or write to another file
}

PL/SQL has similar compact notation for doing a query and looping through the results:

for item in (select * from some_table)
loop
# the name "item" is arbitrary; that variable doesn't need to be declared
# refer to columns using the notation .
end loop;

As the stored procedures get more elaborate, you can get into different syntax like the FORALL statement for issuing lots of INSERT/UPDATE/DELETE statements, or doing BULK COLLECT to pull the full results of a query into a PL/SQL collection variable to inspect the whole thing. But the construct above is fine for most typical query / reporting scenarios.

The similarity between the 2 languages is the reason that I've never used the Perl DBI modules for database work. It's too easy to write out real SQL statements or PL/SQL blocks using a HERE document, invoke SQL*Plus using backticks, do one-liners in Perl to just call PL/SQL stored procedures... just generally hand off the database logic. I even see parallels in the way object-oriented constructs were added to both languages in ways that don't especially appeal to me. (If I want to do object-oriented programming, Ruby is the most appealing choice for me.)