Goal

The goal of the exercise is to remove the global variables that can be accessed by two different threads. Read-only access is fine. When one thread can modify the value while another is reading it, synchronization is necessary.

We remove global variables by any combination of the following:

  1. passing the values as arguments to the routines that need them;
  2. using thread-specific instances of data and retrieving these from the thread structure in different routines that require them (anonymously);
  3. using global variables that provide ``methods'' to access and modify the data; these methods use an instance specific lock/mutex.
In each of these three approaches, it is most convenient to hold the data in a structure rather than as a loose collection of objects. This provides extensibility and allows us to reorganize relatively easily. Additionally, it provides a convenient location for mutex variables. Rather than changing all the code that refers to non-local variables by or both, we can simplify the second step. We use the pre-processor to define the token original with
#define original struct-variable->_original
Now all we need is an appropriate variable named struct-variable in the scope of the access. Again, global variables or changing the routine's signature works. We are now constrained to use the same names as specified in the macro definition.
Note the _ pre-pending the field in the structure. This allows us to ensure we catch all the references correctly.

Structures also allow easy toggling between the threaded and non-threaded case.

Initialization

Some globally accessible variables that are readable and writable do not cause any synchronization problems. These are ones that we can term quasi-constants. They are modified just once from within an intialization routine. These fall in to two categories.
Early initialization
Certain data structures are initialized before any new threads can be created (at the user or internal levels). In this case there is no possibility of race-conditions and so we can proceed in the absence of locks, etc. and ensure that these intializing routines are called early in the process, before new threads are created.

Examples of these types of variables are

Late initialization
Some intialization of global values should not be done unless those facilities will be needed. For example, the color tables for the graphics should only be computed if a graphics window is opened. However, if two or more threads are running, each might initialize the table and we might have two pointers two it, do twice the work, etc. We can use locks to ensure that access to an initialization routine is serialized and the second entrant will have nothing to do. The POSIX threads API provides the routine pthread_once() for this purpose.

The tool nm can be used to determine what symbols are referred to in an object code file and their origin and nature.

Other Directories

Here we just focus on main. However, nmath and appl also have non-local variables. The following table gives the approximate counts of the number of variables that need to be handled in this way in these other directories. These numbers include variables local to a particular routine. An automatic tool might be developed to handle these.
unix80 + system.c, not compiling at present
nmath
appl89 = 75 in cpoly.o and

Non-local Symbols in R's Main Directory.

(ttypd)tigger[main-52]>nm *.o | grep ' [CcDdBb] '
arithmetic.o b hw
arithmetic.o b little_endian
arithmetic.o b lw
Quasi Constants. Initialized in InitArithmetic().
arithmetic.o b lcall
arithmetic.o b naflag
Same old trick: define a local structure containing the fields (prefixed with a _ to ensure no overisght errors) and create instances of these in the different do_() routines. Pass these as arguments to all the routines that share the originally static data.
bind.o b ans_flags
bind.o b ans_length
bind.o b ans_names
bind.o b ans_nnames
bind.o b ans_ptr
These have been aggregated into a locally defined structure (AnswereTypeData) and then an instance of these is created in each of the three do_() routines. The instance is then passed as an argument to the appropriate static routines in this file that populate the fields.
bind.o b count
bind.o b firstpos
bind.o b seqno
The same as above, but with a different structure - ListData.
bind.o b rho do_bind creates a local copy and passes as an additional argument to rbind and cbind.
coerce.o d falsenames
coerce.o d truenames
These are now truly constants.
complex.o b naflag This looks likes it is done. Please check logic.
cov.o b NaFail
cov.o b ZeroSD
Create instances of these in do_cov. ZeroSD is set in the different routines. Modify the signatures for cov_pairwise{1,2} and cov_complete{1,2} to be passed ZeroSD as a pointer so they can pass back the value. Pass NaFail as a flag to complete{1,2} to indicate how to behave in the presence of NAs.
deparse.o b buff
deparse.o d incurly
deparse.o d indent
deparse.o d inlist
deparse.o b len
deparse.o b linenumber
deparse.o d startline
deparse.o b strvec
deparse.o d cutoff
Create a structure R_Deparse and have it contain these fields. Then the usual macros to allow the code not to change but dereference a pointer passed as an argument or local variable. And finally change numerous routines to include a pointer to this structure as an argument.
Outstanding:
deparse1 and deparse2 are not static, but called in numerous places.
Should they compute the deparseOptions variable or be passed it.

Also, cutoff should probably be handled differently (?)

deriv.o b CosSymbol
deriv.o b CoshSymbol
deriv.o b DivideSymbol
deriv.o b ExpSymbol
deriv.o b LogSymbol
deriv.o b MinusSymbol
deriv.o b ParenSymbol
deriv.o b PlusSymbol
deriv.o b PowerSymbol
deriv.o b SinSymbol
deriv.o b SinhSymbol
deriv.o b SqrtSymbol
deriv.o b TanSymbol
deriv.o b TanhSymbol
deriv.o b TimesSymbol
Quasi constants.
deriv.o b exprlist
deriv.o b tag
Same as gcall in devices below. Create local instance of the objects in the do_deriv() routine and pass them to MakeVariable and FindSubExprs
devices.o b gcall Added this as an argument to the single routine that accessed this - SaveString()
dotcode.o d typeinfo These are true constants.
dotcode.o d DupSymbol
dotcode.o d NaokSymbol
Not quite quasi-constants, but could easily be made so. We could use a pthread_once initialization or an explicit up-front initialization.
errors.o d ErrorDB
errors.o d WarningDB
Now consts
errors.o d inError This has been moved to a field in the Evaluator as it is a property of a particular R-level stack. The macro accessing it is in Error.h
format.o b eps
This is curious. In the routines formatReal() and Complex() eps is assigned a value computed from print_digits. I have turned this computation into a macro - COMPUTE_EPS. However, it seems that the computation can be done in scientifc() in-line.
Is there some need to catch the value of print_digits in these two earlier routines and cache the value in eps.

My overall strategy leans towards having a structure that sucks up the different variables in the print.c file controlling the printing. Then an instance of this strucure is associated with each output device/terminal/console or whatever. This would be associated with one or more evaluators and would provide access to these parameters, etc. It would control the locking of the writes so that two threads didn't intermingle their output. A thread might have a stack of these.
The way I finally did this is to put eps into the R_PrintOptions structure that sucks up the variables in the print.c file. The usual defines are available for those variables, but the one for eps is only define in format.c
However, I still think the variable may be unecessary and can be computed on the fly using the COMPUTE_EPS macro.

format.o d tbl This is a simple const array of constants.
graphics.o d HexDigits
graphics.o D ColorDataBase
graphics.o b ColorDataBaseSize
graphics.o C ColorTableSize
graphics.o D DefaultPalette
graphics.o d linetype
graphics.o d nlinetype
const.
graphics.o C ColorTable
graphics.o d R_CurrentDevice
graphics.o C R_Devices
graphics.o D R_NumDevices
graphics.o C nullDevice
graphics.o b ColBuf
graphics.o b adjsave
graphics.o b annsave
graphics.o b bgsave
graphics.o b btysave
graphics.o b cexaxissave
graphics.o b cexbasesave
graphics.o b cexlabsave
graphics.o b cexmainsave
graphics.o b cexsave
graphics.o b cexsubsave
graphics.o b colaxissave
graphics.o b collabsave
graphics.o b colmainsave
graphics.o b colsave
graphics.o b colsubsave
graphics.o b crtsave
graphics.o b errsave
graphics.o b fgsave
graphics.o b fontaxissave
graphics.o b fontlabsave
graphics.o b fontmainsave
graphics.o b fontsave
graphics.o b fontsubsave
graphics.o b labsave
graphics.o b lassave
graphics.o b ltysave
graphics.o b lwdsave
graphics.o b mgpsave
graphics.o b mkhsave
graphics.o b pchsave
graphics.o b srtsave
graphics.o b tcksave
graphics.o b xaxpsave
graphics.o b xaxssave
graphics.o b xaxtsave
graphics.o b xpdsave
graphics.o b yaxpsave
graphics.o b yaxssave
graphics.o b yaxtsave
ColBuf is just used as a temporary buffer. Thus, I have changed RGB2rgb and col2name to pass in its own scratch buffer which is populated appropriately. In fact, in col2nam, this buffer is only used if the color is not in the color database. If NULL is passed, a buffer is allocated and returned. This incurs the cost of retrieving the evaluator from the thread specific data.

Make sure InitColors is only called once.

list.o b IncludeFunctions
list.o b ItemCount
list.o b MaxCount
list.o b StoreValues
list.o b UniqueNames
list.o b ans
Gather these fields into a structure and add a pointer to the struct as an argument to namewalk. Then create a local copy of the object in do_allnames
logic.o b haveFalse
logic.o b haveNA
logic.o b haveTrue
This one is simple. Aggregate the three variables into a structure (which I called CantThinkOfAName; please change!) and provide the usual definitions. Instantiate this structure in do_logic3. Then modify the signature for checkValues(). This is only called by do_logic3, so only those calls need to be changed.
main.o b BrowsePrompt
main.o b prompt_type
These two have been moved to the R_IO component in the Evaluator.
I also changed the name of prompt_type to promptType. The reason is that it is now a macro that gets included in every file. It appears that gram.y uses a local variable named prompt_type. So, we have to turn it off. If this poses a problem with other code, we can return to using prompt_type as the name of the macro and #undef it in gram.y
main.o b doneit
main.o C R_Bracket2Symbol
main.o C R_BracketSymbol
main.o C R_ClassSymbol
main.o C R_CommentSymbol
main.o C R_DimNamesSymbol
main.o C R_DimSymbol
main.o C R_DollarSymbol
main.o C R_DotsSymbol
main.o C R_DropSymbol
main.o C R_LastvalueSymbol
main.o C R_LevelsSymbol
main.o C R_ModeSymbol
main.o C R_NaRmSymbol
main.o C R_NamesSymbol
main.o C R_RowNamesSymbol
main.o C R_SeedsSymbol
main.o C R_TspSymbol

main.o C R_tmp
main.o C R_NaN
main.o C R_PosInf
main.o C R_NegInf
main.o C R_NaInt
main.o C R_NaReal
main.o C R_NaString
main.o C R_BlankString

main.o C R_MissingArg
main.o C R_NilValue
main.o C R_UnboundValue
memory.o b C_Pointers
memory.o d gc_count
memory.o D gc_inhibit_torture
memory.o d gc_reporting
model.o d colonSymbol
model.o d dotSymbol
model.o d identSymbol
model.o d inSymbol
model.o d minusSymbol
model.o d parenSymbol
model.o d plusSymbol
model.o d powerSymbol
model.o d slashSymbol
model.o d tildeSymbol
model.o d timesSymbol
These are reinitialized each call to the models. This is ok if install is synchronized, which it has to be. The concern is performance since the synchrnoization may slow everything down.
Perhaps a vectorized call to install would be a useful addition. This would lock and get all the symbols.

The install table must have a reader-writer lock to be efficient.

model.o b framenames
model.o b intercept
model.o b nterm
model.o b nvar
model.o b nwords
model.o b parity
model.o b response
model.o b varlist
Usual structure and defines approach. There is an issue now of where we create a new one R_Model object. Presumably in the different do_? routines. But there is a also a routine CheckRHS which is public that requires an instance of the currentModel. This actually appears to be never called by any R function or other routine. So it seems to be static (or intended for use in contributed code/libraries).
Note that in do_modelmatrix there are local variables with the same names as the original static ones. Thus the new macro access to these takes over and all sorts of errors appear. Thus at the top of that routine (which fortunately happens to be the last in the file), we undef the pertinent macro accessors.
optimize.o b R_env
optimize.o b R_env1
optimize.o b R_env2
optimize.o b R_fcall
optimize.o b R_fcall1
optimize.o b R_fcall2
The usual idea partiall works here. We gather each of these pairs of {function, environment} and create a new structure just for those. We do this rather than having one structure just for guaranteed correctness (i.e. get the compiler to typecheck) and the non-linear version seems to be expanding to handle derivative functions.
To allow recursive calls, each of the structures contains a pointer to another element of the same type. In this way, we have a stack or linked list. Now, an R-function can call the appropriate entry point recursively and pop the new function and environment onto the top of the list. This is extremely simple: check the current value; if it is NULL set it equal to the new value; otherwise, set the next field of the new value to the current value of the variable and set the variable to this new value. When that call completes, pop the local value off the top of this list. (I.e. it is a simple linked-list.)
This approach works in both the threaded and non-threaded case.

The reason the approach only partially works is that the top-level refer to other routines fcn{,1,2} whose call signature is fixed externally. Thus, we can't pass the current value of the user function and environment or the current evaluator. Thus those routines must compute these values by either using

  • global variables in the non-threaded case, and
  • thread-specific data tables in the threaded case.
The latter concerns me for efficiency purposes, but the alternative is to have a field in the evaluator which holds the current values of these variables.
par.o b gcall Modify the signature for the lengthCheck routine to take the SEXP that is gcall. This is invoked (regularly!) from Specify and Specify2, so the gcall object is passed to these from do_par().

Making lengthCheck a macro

#define LengthCheck(n) lengthCheck(what, value , n, gcall)
would be simpler.
A single call before any processing that retrieved n from a table with the par element as keys would be even easier.
plot.o b dnd_hang
plot.o b dnd_hght
plot.o b dnd_llabels
plot.o b dnd_lptr
plot.o b dnd_n
plot.o b dnd_offset
plot.o b dnd_rptr
plot.o b dnd_xpos
The usual stucture/define approach works very simply here. We create separate local copies in do_dend and do_dendwindow and pass these to drawdend which is the only routine that needs to be modified.

I am guessing that this has something to do with a dendogram. (Consistent with the small number of routines involved in the spirit of recursion.)

plot3d.o b VT
plot3d.o b ctr_SegDB
plot3d.o b ctr_xtol
plot3d.o b ctr_ytol
Usual structure/define. Change the different routines such as Rotate, Accumulate, etc.
plot3d.o b gcall
Local instance of this in do_persp. However, it is never actually used. The only routine that refers to is CheckRange which is ifdef'ed away.
plot3d.o d Face
plot3d.o d Vertex
These are constant arrays of constants.
plotmath.o d AccentTable
plotmath.o d BinTable
plotmath.o d ItalicFactor
plotmath.o d MetricUnit
plotmath.o d OpTable
plotmath.o D RelTable
plotmath.o d SymbolTable
All of these are now read-only. They are simple constants or tables of constants.

I also changed the definitions for some of the structs to qualify the fields with a const. For example, SymTab. Everything compiles, so all is clea{n,r}er.

plotmath.o d BaseCex
plotmath.o b MathDevice
plotmath.o b BoxColor
plotmath.o b CosAngle
plotmath.o b CurrentAngle
plotmath.o b CurrentStyle
plotmath.o b CurrentX
plotmath.o b CurrentY
plotmath.o b ReferenceX
plotmath.o b ReferenceY
plotmath.o b SinAngle
plotmath.o b TextColor
Modified most of the render routines, etc. to take a new argument.
plotmath.o d FiveEighteenths.130
plotmath.o d OneEighteenth.133
plotmath.o d OneSixth.124
plotmath.o d TwoNinths.127
Const values. Now consts
print.o b tagbuf
print.o C R_print_width
print.o C print_digits
print.o C print_gap
print.o C print_na_string
print.o C print_na_width
print.o C print_quote
print.o C problem_buf
Unhappy with the way intpr and dblepr (and a few others) have to compute the evaluator and then the print options.

These are converted to a print options/settings structure. I imagine that this will be a field in the evaluator. For most routines that access these, this can be retrieved using macros. The format*() and print*Vector routines do not receive the evaluator argument however. Also, EncodeComplex LeftMatrixColumnLabel RighMatrixColumnLabel So we need to determine whether we want to pass that or the options themselves or have them computed internally.
That is what I have done. We keep things as flexibile as possible by passing the print options themselves so that one doesn't have to create a new evaluator or swap the new print options with the current ones when invoking these routines. (The latter suffers from complicated error handling needed to restore the original values).

printutils.o b Encodebuf In short, those routines that used to access Encodebuf now are passed a scratch buffer.

This is one of the few static variables that doesn't lend itself to a structure/define approach or changing the signature of the routines to pass this as a variable. The reason is that that there are 134 references to the Encode* routines in the R source. Thus we would have to change a lot of routines to support passing a local buffer. Another reason is that the semantics of persistent values in this buffer is complicated by this dstributed invocation network.

As a result of these complications and the important nature of these routines (and potential for being invoked elsewhere in user contributed code), It would be natural to adopt a simpler approach. This adds the Encodebuf variable to the evaluator structure and thus makes it evaluator-specific (which is almost thread-specific). Since we also have print options in the evaluator, we can add it to this rather than the actual evaluator structure.

The problem with this is that these routines do not take the Evaluator as an argument.

By creating local scratch buffers that are passed to the different routines, the executable consumes more memory that may never be used. Putting this buffer into the evaluator makes it unique and thus reduces the memory required. However, since there are almost an equal number of routines that don't have access to the evaluator when calling the routines to which the buffer must be passd, the approach is complicated. Also, it is not very local.

Recursive calls can be done by making this a simple linked list and redefining the macros accessing this. However, this approach does prohibit recursive calls that don't access the result in a simple order.

Rsprintf now has to allocate space. For this it also needs access to the evaluator which is not passed to it. So it must retrieve it using thread-specific data. Think about changing this to pass the buffer.

random.o d naflag Create a local naflag in each of the do_random{1,2,3}. Then pass this to the different random{1,2,3} as a pointer. These set the value if necessary.
relop.o b rcall Instantiate this in do_relop and pass it to complex_relop which is the only routine that needs it.
saveload.o b InComplex
saveload.o b InInit
saveload.o b InInteger
saveload.o b InReal
saveload.o b InString
saveload.o b InTerm
saveload.o b NSave
saveload.o b NSymbol
saveload.o b NTotal
saveload.o b NVSize
saveload.o b NewAddress
saveload.o b OldOffset
saveload.o b OutComplex
saveload.o b OutInit
saveload.o b OutInteger
saveload.o b OutNewline
saveload.o b OutReal
saveload.o b OutSpace
saveload.o b OutString
saveload.o b OutTerm
saveload.o b VersionId
saveload.o b buf
saveload.o b bufp
saveload.o C xdrs
Some routines are public and called from MS-windows and unix related code. It is not yet clear whether
  1. These are passed the parameters as a argument
  2. create their own
  3. the structure is part of the evaluator.
The final decision is likely related to the thread model and the flexibility we want to provide and tolerate in creating such calls! It is related to the printing, graphics, options, etc. - the inter-evaluator communication and inheritance model.

I had to change some of the InXdr..() routines to take an unecessary argument. This is because the other In...() require this and since both types are assigned to the same function pointer, they must have the same signature. These are local/static and are now changed.

Similarly, the Technically these only need the xdrs object but for the same reason as in the previous paragraph, we have to pass access to the entire parameter structure.
So in short, I added a pointer to an R_Serialize structure as an argument to each of the In and Out routines. This seems like a big change with much redundancy, but it is extensible, providing a vehicle in which to put new data fo use in new I/O setups (e.g the xdrs in RPC, serialization of objects in Java/RMI, CORBA, etc.)

(I also moved the include of the RPC material header to the top of the file).

scan.o b ConsoleBuf
scan.o b ConsoleBufCnt
scan.o b ConsoleBufp
scan.o b ConsolePrompt
The ConsoleBuf and Prompt variables are fields in a structuture, with usual defines. Local versions are created in each of the do_readline do_menu do_scan and do_countfields and passed to the different routines such as expected scanFrame extractItem, etc. as a pointer to an instance of a R_Scan.
scan.o b NAstrings
scan.o b fp
scan.o b quiet
scan.o d save
scan.o d sepchar
scan.o b ttyflag
Same old story here too. However, it might useful to connect the two new structures in scan.c so that one contains the other. In that way, we could reduce the number of arguments to some routines by being able to compute the params slot from the scan structure or vice-versa. At the moment, it is a more flexible approach, just less parsimonious.
subassign.o b gcall This is like the gcall in devices.c, but with a slight difference. The idea is to take the SEXP from the do_() routine and store it for access by the different routines in the call stack below this routine. However, it turns out that the only place it is used is when there is an error (the default: case of a switch statement in SubassignTypeFix). It seems a shame to have to modify the call signatures for the intermediate routines the may call this routine for such an unusual case. There are two alernatives to doing this.
  1. Use thread-specific data. The do_() routine would squirrel the call away and go about its business in the usual way. If the default statement of the switch was invoked, it would retrieve this thread specific data.
    The only real penalty is the initial caching of the data into the thread's data table.
  2. Alternatively, we could create a field in the evaluator for this information. There is almost no run-time cost associated with this unlike the the thread-specific data. It amounts to the same thing due to our thread = evaluator model. However, it really doesn't belong in the evaluator.
One problem with either of these approaches is the nested calls to this do_() routine or the potential of parallelizing the evaluator. We may require two instances of these. The nested calls case is not too hard to handle using a stack of these objects (SEXPs). Caching the data retrieves (and creates as necessary) a stack and pushes the value onto the top. The error code peeks at it without popping it. The do_() routine pops it when it is complete.
Error handling of course is an issue. We must ensure that if an unforeseen error occurs so that the do_() routine does not terminate normally that the stack is correctly modified.

In spite of this (post-fact) discussion, I did change the signatures to pass the argument throught to the different lower-level routines.

summary.o b narm
summary.o b updated
There are just two variables that are required by most of the different worker routines called from do_summary. Rather than passing both of these, we create a structure and pass a pointer to it.
unique.o b HashTable
unique.o b K
unique.o b M
unique.o b equal
unique.o b hash
unique.o b nomatch
Usual approach. Convert these fields into a structure and provide defines. Then update signatures of the different routines that need access the fields to pass the a pointer to the structure as an argument.

Need to determine what to do with the public routines match, do_match and duplicated.

util.o d TypeTable
util.o d falsenames
util.o d truenames
util.o d type_msg
Consts

Duncan Temple Lang <duncan@research.bell-labs.com>
Last modified: Mon Oct 26 08:22:35 EST 1998